[최단 경로] 백준 11779번 : 최소비용 구하기 2 / 골드 3

https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

다익스트라 + 경로 직접 구하기 문제이다.

힙에 cost + w, next 뿐만 아니라 cur 노드도 넣어준다. 

그리고 힙에서 하나씩 꺼내면서 처음 방문한 노드에 도착하면

딕셔너리 구조에 이전 노드, 현재 노드를 저장해준다.

다익스트라가 끝난 후 딕셔너리를 이용해 목적지부터 역순으로 경로를 추적하면 된다.

 

웰노운 문젠데 좀 오래 걸렸다.. 정신차리자.

import collections
import heapq

n = int(input())
m = int(input())

graph = collections.defaultdict(list)
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append([v, w])

start, fin = map(int, input().split())

q = []
heapq.heappush(q, [0, start, 0])
dist = [-1 for _ in range(n)]

prev_dct = {}

while q:
    cost, cur, prev = heapq.heappop(q)
    if dist[cur-1] == -1:
        dist[cur-1] = cost

        prev_dct[cur] = prev

        if cur == fin:
            break

        for next, w in graph[cur]:
            heapq.heappush(q, [cost + w, next, cur])

print(dist[fin-1])

route = []
while fin != start:
    route.append(fin)
    fin = prev_dct[fin]
route.append(start)

print(len(route))
print(*reversed(route))