[백준] 1162. 도로포장

✍🏻코드

import heapq
INF = 98765432109876543210

n,m,k = map(int,input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))
q = []
distance = [[INF]*(k+1) for _ in range(n+1)]

for i in range(k+1):
    distance[1][i] = 0
heapq.heappush(q,(0,1,0))

while q:
    dist,now,p = heapq.heappop(q)
    if dist > distance[now][p]:
        continue
    if p+1 <= k:
        for idx,x in graph[now]:
            if distance[idx][p+1] > dist:
                distance[idx][p+1] = dist
                heapq.heappush(q,(dist,idx,p+1))
    for idx,x in graph[now]:
        cost = x + dist
        if distance[idx][p] > cost:
            distance[idx][p] = cost
            heapq.heappush(q,(cost,idx,p))
answer = INF
for i in range(k+1):
    answer = min(distance[n][i],answer)
print(answer)

💡풀이

• 노드(도시)에서 노드 끝까지 최단 경로를 구하는 다익스트라 알고리즘으로 풀 수 있다.
• 대신, 각 경로간 k번만큼 도로 포장을 해서 거리를 0으로 만들수 있다.
• 기존 다익스트라 알고리즘으로 푸는 문제에서 해당 노드까지의 최단거리를 저장해두는 배열을 k+1개만큼 생성해서, 각 인덱스에 도로 포장을 한 횟수당 최단 경로를 저장한다.
• 그리고 현재 포장한 횟수의 인덱스까지 힙큐에 넣고, 포장을 더 할 수 있으면 idx번 도시까지의 거리 x를 0으로 만들 수 있다.