import sys
input = sys.stdin.readline
from heapq import heappush,heappop
INF=sys.maxsize
N,M,K = map(int,input().split())
graph = [[] for i in range(N)]
for i in range(M):
x,y,w = map(int,input().split())
graph[x-1].append((y-1,w))
graph[y-1].append((x-1,w))
DP = [[INF]*N for i in range(K+1)]
hq = []
heappush(hq,(0,0))
while hq:
w,now = heappop(hq)
if DP[0][now] <= w:
continue
DP[0][now] = w
for next,w1 in graph[now]:
heappush(hq,(w+w1,next))
for k in range(1,K+1):
hq = []
heappush(hq,(0,0))
while hq:
w,now = heappop(hq)
if DP[k][now] <= w:
continue
DP[k][now] = w
for next,w1 in graph[now]:
heappush(hq,(DP[k-1][now],next))
heappush(hq,(w+w1,next))
print(DP[K][N-1])
아이디어를 떠올리기 쉽지 않았던 문제, 다 익스트라 + DP로 해결하였다.
K의 숫자가 작기 때문에 다 익스트라를 K+1번 실행하여 결과를 구하였다.
알고리즘을 요약하면,
1. 다 익스트라를 K+1번 하는데, 처음에는 정상적으로 실행한다.
2. 두번째부터 다 익스트라를 할 때, w+w1의 값과 이전 DP값+0값 두번 넣는다.
4. K+1번 다 익스트라를 실행하여 최솟값을 출력한다.
오늘의 교훈) 다 익스트라를 할 때 INF의 크기를 조심하자 (1e9로 했다가 낭패봤다)