문제

[백준] 최소비용 구하기 2 (Gold 3)

요약

N개의 도시가 있다. 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. A번째 도시에서 B번째 도시까지 가는 데 드는 최소 비용과 경로를 출력하라. (1 <= N <= 1,000, 1 <= M <= 100,000)

분류

  • 다익스트라

풀이

내 풀이 (다익스트라)

다익스트라 알고리즘으로 경로를 추적하는 대표적인 문제이다.

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

n = int(input())
m = int(input())

graph = [[] for _ in range(n)]

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

start, end = map(lambda x: int(x) - 1, input().split())

d = [sys.maxsize] * n
d[start] = 0
path = [0] * n

queue = [(0, start)]

while queue:
    w, i = heappop(queue)

    if d[i] < w:
        continue

    if i == end:
        break

    for node, weight in graph[i]:
        if d[i] + weight < d[node]:
            d[node] = d[i] + weight
            heappush(queue, (d[node], node))
            path[node] = i  # 직전 노드 기록

x = end + 1
ans = [x]

while x != start + 1:
    x = path[x - 1] + 1
    ans.append(x)

print(d[end])
print(len(ans))
print(*ans[::-1])