[백준 1162번] 도로포장 (Python3)

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로 했다가 낭패봤다)