알고리즘: 백준 11779번 최소비용 구하기2 (feat.python)

 

11779번: 최소비용 구하기 2

 

import sys
import heapq
read = sys.stdin.readline
n = int(read())
m = int(read())
graph = {i:[] for i in range(1, n+1)}
for _ in range(m):
    s, e, w = map(int, read().split())
    graph[s].append([w, e])

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

INF = sys.maxsize
dist = [[INF, 0] for _ in range(n+1)]
dist[start] = [0, start]
hq = []
heapq.heappush(hq, [0, start])
route = []

def dijkstra():
    while hq:
        cw, cn = heapq.heappop(hq)
        for nw, nn in graph[cn]:
            next_weight = nw + cw
            if next_weight <= dist[nn][0]:
                dist[nn] = [next_weight, cn]
                heapq.heappush(hq, [next_weight, nn])

def find_route(end):
    route.append(end)
    if end != start:
        find_route(dist[end][1])

dijkstra()
find_route(end)
route = route[::-1]

print(dist[end][0])
print(len(route))
for r in route:
    print(r, end=' ')