[백준 11779] 최소비용 구하기 2 python

11779번 - 최소비용 구하기 2

문제 이해

방향 가중치 그래프에서 최단경로를 찾는 문제.
최단거리(비용)만 구하면 되는 것이 아닌 그 경로 또한 찾아야 한다.

접근

다익스트라로 최소비용을 구하는 동시에 경로를 기록하기 위해 거리가 갱신될 때 어떤 노드에서 왔는지 기록해준다.

정답 코드

import sys
from heapq import *
input = sys.stdin.readline
INF = int(1e9)

n = int(input())
graph = [[] for _ in range(n+1)] # 도시 번호는 1부터 시작
for _ in range(int(input())):
    u, v, c = map(int, input().split())
    graph[u].append((v, c)) # 방향 그래프
departures, arrivals = map(int, input().split())

# Dijkstra
dist = [INF for _ in range(n+1)]
prev = [-1 for _ in range(n+1)]
dist[departures] = 0
hq = []
heappush(hq, (0, departures))

while hq:
    cur_dist, cur = heappop(hq)
    if dist[cur] < cur_dist: continue
    for nx, nx_dist in graph[cur]:
        if dist[nx] > cur_dist + nx_dist:
            dist[nx] = cur_dist+nx_dist
            heappush(hq, (dist[nx], nx))
            prev[nx] = cur # cur -> nx를 기록해 이후 역추적

# 경로 추적
route = [arrivals]
cur = arrivals
while prev[cur] != -1:
    route.append(prev[cur])
    cur = prev[cur]


# Print result
print(dist[arrivals])
print(len(route))
print(*route[::-1]) # 역순으로 출력해야함