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

💡문제접근

• 일반적인 다익스트라 알고리즘처럼 최단거리를 출력하면서 최단 경로를 역추적해야하는 문제였다. 다익스트라의 역추적에 대해서 공부하고 다시 풀었다. 최단거리를 계산하는 것 뿐만 아니라 해당 경로도 출력할 수 있도록 하는 부분도 알아두자.

💡코드(메모리 : 137860KB, 시간 : 560ms)

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
parent = [0] * (n+1)
distance = [INF] * (n+1)
for _ in range(m):
    a, b, c = map(int, input().strip().split())
    graph[a].append([b, c])
s, e = map(int, input().strip().split())

def dijkstra(start):
    q = []
    heapq.heappush(q, [0, start])
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for next_node, next_dist in graph[now]:
            cost = dist + next_dist
            if distance[next_node] > cost:
                distance[next_node] = cost
                parent[next_node] = now
                heapq.heappush(q, [cost, next_node])
    return distance

res = dijkstra(s)
print(res[e])
path = []
destination = e
while destination:
    path.append(destination)
    destination = parent[destination]
print(len(path))
print(*path[::-1])

💡소요시간 : 2h