풀이

• 이번엔 다익스트라에 경로까지 탐색하는 방법이다.
• 이전에 LIS나 경로 찾기에 관해 문제를 풀어본 경험이 있어서 대충 감은 왔는데 너무 오래되어 잊어버린 듯 하다.
• 복기하면서 문제를 풀이하였고, 마지막에 출력하는 방법까지 숙지하였다.

코드

import heapq
from collections import defaultdict
INF = float('INF')

n = int(input())
m = int(input())
graph = defaultdict(list)
distance = [INF] * (n+1)
prev = [0] * (n+1)

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

s, e = map(int, input().split())

def dijkstra(s):
    q = []
    heapq.heappush(q, (0, s))
    distance[s] = 0

    while q:
        cur_dist, cur_node = heapq.heappop(q)
        if distance[cur_node] < cur_dist:
            continue
        
        for next_node, next_dist in graph[cur_node]:
            cost = cur_dist + next_dist
            if cost < distance[next_node]:
                distance[next_node] = cost
                prev[next_node] = cur_node
                heapq.heappush(q, (cost, next_node))

dijkstra(s)

print(distance[e])
path = [e]

now  = e
while now != s:
    now = prev[now]
    path.append(now)

print(len(path))
print(*path[::-1])