백준 11779 - 최소비용 구하기 2 (파이썬)

Answer

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
INF = float('inf')

n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]
dp = [INF] * (n + 1)
trace = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

start, end = map(int, input().split())
trace[start].append(start)

def dijkstra(start):
    q = [(start, 0)]
    dp[start] = 0
    
    while q:
        now, now_cost = heappop(q)

        if now_cost <= dp[now]:
            for next, next_cost in graph[now]:
                sum_cost = now_cost + next_cost
                
                if sum_cost < dp[next]:
                    dp[next] = sum_cost
                    trace[next] = now
                    heappush(q, (next, sum_cost))

                    trace[next] = trace[now] + [next]
                
dijkstra(start)
print(dp[end])
print(len(trace[end]))
print(*trace[end])