[백준/python/1854] k번째 최단경로 찾기

문제링크 : k번째 최단경로 찾기

최소비용 문제=>대부분 다익스트라
다익스트라 문제는 여러 문제를 접하면서 패턴을 익히는 게 중요한 것 같다.

import sys
import heapq

input=sys.stdin.readline
n,m,k=map(int, input().split())
inf=sys.maxsize

graph=[[]for _ in range(n+1)]
dp=[[inf]*k for _ in range(n+1)]
heap=[]

def dij(start):
    heapq.heappush(heap,[0,start])
    dp[start][0]=0
    while heap:
        w,n=heapq.heappop(heap)
        for n_n,wei in graph[n]:
            n_w=wei+w
            if n_w<dp[n_n][k-1]:
                dp[n_n][k-1]=n_w
                dp[n_n].sort()
                heapq.heappush(heap, [n_w,n_n])

for _ in range(m):
    a,b,w=map(int, input().split())
    graph[a].append([b,w])

dij(1)

for i in range(1,n+1):
    if dp[i][k-1]==inf:
        print(-1)
    else:
        print(dp[i][k-1])

dp[i]에 k개의 공간을 만들어 값을 넣고 정렬한 후 마지막 값=1부터 i까지 k번째 최단 경로
이것만 명심하면 다른 다익스트라 문제와 같다.