백준 #11779 최소비용 구하기 2 (파이썬)

문제 링크

아주 전형적인 다익스트라 문제다.
하지만 최단 비용만 출력하는 게 아니라 그때의 경로를 함께 출력해야 하므로 추가 변수가 필요하다.

대부분의 경우 dist와 함께 prev_node 리스트를 만든다.
end에서 이전 노드를 계속 거슬러 올라가다보면 start가 나오고,
그게 곧 경로이기 때문이다.

dijkstra 함수의 구현 방법에 대해서는 https://velog.io/@yoopark/shortest-path-implement 참고 바랍니다.

# 경로가 있는 다익스트라

import sys
from collections import defaultdict
import heapq
INF = int(1e9)

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
graph = defaultdict(list)
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append((b, c))
start, end = map(int, sys.stdin.readline().rstrip().split())

dist = [INF] * (n+1)
prev_node = [0] * (n+1)

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dist[start] = 0
    while q:
        weight, node = heapq.heappop(q)
        if dist[node] < weight:
            continue
        for adj_node, adj_weight in graph[node]:
            cost = weight + adj_weight
            if cost < dist[adj_node]:
                dist[adj_node] = cost
                prev_node[adj_node] = node
                heapq.heappush(q, (cost, adj_node))

dijkstra(start)
print(dist[end])

path = [end]
now = end
while now != start:
    now = prev_node[now]
    path.append(now)

path.reverse()

print(len(path))
print(' '.join(map(str, path)))