BOJ 10217 KCM Travel python

다익스트라, dp를 사용하여 풀이. [cost]*[v]로 dp를 설정했다. 다음 방문 노드까지의 비용이 m 이하이고, 비용이 dp에 저장된 값보다 작으면 dp를 갱신하고 큐에 넣어준다.

dp 구현 아이디어와 dp를 갱신 아이디어가 중요한 문제였다. 시간 제한이 아슬아슬해서 큐에서 뽑은 현재 거리와 dp에 저장된 거리를 비교해, 케이스를 줄이는 과정도 필요했다.

풀이 코드

import sys, heapq
rl = sys.stdin.readline
tn = int(rl())
for _ in range(tn):
    n, m, k = map(int, rl().split())
    g = [[] for _ in range(n)]
    for _ in range(k):
        u,v,c,d = map(int, rl().split())
        g[u-1].append((v-1,c,d))
 
    dp = [[sys.maxsize for _ in range(n)] for _ in range(m+1)]
    dp[0][0] = 0
    q = [(0,0,0)]
    while q:
        time, node, money = heapq.heappop(q)
        if dp[money][node] < time: continue
        
        for nnode, dm, dt in g[node]:
            if money+dm <= m:
                if dp[money+dm][nnode] > time+dt:
                    for i in range(money+dm, m+1):
                        if dp[i][nnode] > time+dt:
                            dp[i][nnode] = time+dt
                        else: break
                    heapq.heappush(q, (time+dt, nnode, money+dm))
    print(dp[m][-1] if dp[m][-1]!=sys.maxsize else "Poor KCM")