[백준 10217] KCM Travel - Python(파이썬)

다익스트라와 냅색을 활용한 코드

from heapq import heappop, heappush
import sys


def solution():
    check = [[float('inf')] * (M+1) for _ in range(N+1)]
    temp = [(0, 0, 1)]

    while temp:
    	# d: 거리, c: 비용, idx: 해당 인덱스
        d, c, idx = heappop(temp)
        if check[idx][c] < d:
            continue
        # 원하는 인덱스면, 해당 거리 리턴!
        if idx == N:
            return d
        # k: 해당 인덱스, l: 비용, m: 거리
        for k, l, m in dist[idx]:
            l += c
            m += d
            # 합 비용이 예산 초과거나  합 거리가 check의 거리 이상일 경우, continue
            if M < l or check[k][l] <= m:
                continue
            # 중복 줄이기 핵심
            for i in range(l, M+1):
                if check[k][i] > m:
                    check[k][i] = m
                else:
                    break
            heappush(temp, (m, l, k))
            
    return 'Poor KCM'


T = int(sys.stdin.readline().strip())
for tc in range(T):
    N, M, K = map(int, sys.stdin.readline().split())
    dist = {i: [] for i in range(N+1)}

    for _ in range(K):
        u, v, c, d = map(int, sys.stdin.readline().split())
        dist[u].append((v, c, d))

    print(solution())