BOJ 11779 최소비용 구하기 2

https://www.acmicpc.net/problem/11779
시간 1초, 메모리 256MB

input :

• n (1 ≤ n ≤ 1,000)
• m (1 ≤ m ≤ 100,000)
• a b cost
• start end

output :

• 최소 비용을 출력
• 경로에 포함되어있는 도시의 개수를 출력
• 경로를 방문하는 도시 순서대로 출력

조건 :

• A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화
• A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하

---

idea

주의

마지막에 route를 저장할 때는 뒤에서 부터 넣으니까 reverse()를 꼭 잊지 말자.

import sys
from heapq import heappop, heappush

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = [[] for _ in range(n + 1)]
prev_node, distance = [-1] * (n + 1), [float("inf")] * (n + 1)

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

start, end = map(int, sys.stdin.readline().split())
q = []
heappush(q, (0, start))
distance[start] = 0

while q:
    now_dist, now_node = heappop(q)

    if distance[now_node] < now_dist:
        continue

    for cost, next_node in graph[now_node]:
        if now_dist + cost < distance[next_node]:
            heappush(q, (now_dist + cost, next_node))
            distance[next_node] = now_dist + cost
            prev_node[next_node] = now_node

route = [end]
now_node = end
while now_node != start:
    now_node = prev_node[now_node]
    route.append(now_node)
route.reverse()

print(distance[end])
print(len(route))
print(*route)