백준최소비용구하기2_11779골드3

코드

import heapq as hq
import sys
import copy

INF = int(1e9)
N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)]
path = [[] for _ in range(N+1)]
distance = [INF]*(N+1)

for i in range(M) :
    s,e,c = map(int,sys.stdin.readline().split(" "))
    graph[s].append((e,c))

start_node,end_node = map(int,sys.stdin.readline().split(" "))

# 다익스트라 시작
queue = []
distance[start_node] = 0
hq.heappush(queue,(distance[start_node],start_node))

while queue :
    current_distance,current = hq.heappop(queue)
    if distance[current] < current_distance :
        continue
    path[current].append(current)
    for adj_node,adj_cost in graph[current] :
        current_cost = current_distance + adj_cost
        if current_cost < distance[adj_node] :
            distance[adj_node] = current_cost
            hq.heappush(queue,(distance[adj_node],adj_node))
            path[adj_node] = copy.deepcopy(path[current])

print(distance[end_node])
print(path)
print(len(path[end_node]))
print(*path[end_node])

경로까지 구할 수 있어서 좋았습니다.

결과