BOJ - 9870 - Vacation Planning

import sys

INF = 1e9
MAX = 201

def solution():
    cnt, sum = 0, 0
    N, M ,K, Q = map(int, sys.stdin.readline().split())
    matrix = [[INF for _ in range(MAX)] for _ in range(MAX)]

    for _ in range(M):
        U, V, D = map(int, sys.stdin.readline().split())
        matrix[U][V] = D

    for i in range(MAX):
        for j in range(MAX):
            if i == j: matrix[i][j] = 0

    for k in range(N+1):
        for i in range(N+1):
            for j in range(N+1):
                matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])

    for i in range(Q):
        U, V = map(int, sys.stdin.readline().split())
        cost = INF
        for j in range(K+1):
            cost = min(cost, matrix[U][j] + matrix[j][V])
        if cost != INF:
            cnt += 1
            sum += cost

    print(cnt)
    print(sum)
solution()

https://www.acmicpc.net/problem/9870