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

놓친점

1. 경로복원

• index값에 해당하는 노드에 도달하기 전 노드가 어떤 노드인지 기록하면 됨

# 초기화
pre_ = [0]*(v+1)

...

# 최단 거리값 갱신될 때 pre_ 테이블에 이전 방문 노드 값 변경
for next_node, weight in graph[now]:
    cost  = weight+dist
    if distance[next_node]>cost:
        distance[next_node] = cost
        # 어떤 노드를 타고 왔는지 pre_ 테이블에 기록
        pre_[next_node] = now
        heappush(heap,(cost, next_node))

2. 경로 출력
   pre[end] = mid
   
   pre[mid] = mid
   
   ...
   
   pre[mid] = start
   
   pre[start] = 0 # pre_ 테이블 초기화 값

route = []
while end!=0:
    route.append(end)
    end = pre_[end]
# route 리스트에 end -> start 순으로 요소 나열됨
route.reverse()

제출 코드

import sys
from heapq import heappop, heappush
input = sys.stdin.readline
INF = int(1e9)

v = int(input())
e = int(input())
graph = [[] for _ in range(v+1)]
distance = [INF]*(v+1)
pre_ = [0]*(v+1)
heap = []
route = []

# 그래프 초기화
for _ in range(e):
   s,e,c = map(int, input().split())
   # 목적지 노드, 가중치
   graph[s].append((e,c))

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

def dijkstra(start):
   distance[start] = 0
   # 우선순위 : 거리/가중치, 노드 번호
   heappush(heap,(0,start))
   
   while heap:
       dist, now = heappop(heap)
       
       if distance[now]<dist:
           continue
       for next_node, weight in graph[now]:
           cost  = weight+dist
           if distance[next_node]>cost:
               distance[next_node] = cost
               # 어떤 노드를 타고 왔는지 pre_ 테이블에 기록
               pre_[next_node] = now
               heappush(heap,(cost, next_node))
               
dijkstra(start) 
print(distance[end])
while end!=0:
   route.append(end)
   end = pre_[end]

route.reverse()
print(len(route))
print(" ".join(map(str, route)))