백준 10217 - KCM Travel (파이썬)

Answer

from sys import stdin

input = stdin.readline
INF = int(1e9)

def dijkstra():
    dp = [[INF] * (M + 1) for _ in range(N + 1)]
    dp[1][0] = 0
    
    for cost in range(M + 1):
        for current in range(1, N + 1):
            if dp[current][cost] == INF:
                continue

            for next, next_c, next_d in graph[current]:
                total = cost + next_c
                if total <= M:
                    dp[next][total] = min(dp[next][total], dp[current][cost] + next_d)
    
    return dp

for _ in range(int(input())):
    N, M, K = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    
    for __ in range(K):
        u, v, c, d = map(int, input().split())
        graph[u].append((v, c, d))

    answer = min(dijkstra()[N])
    
    if answer == INF:
        print('Poor KCM')
    else:
        print(answer)

pypy3로 제출하셔야 합니다.