Baekjoon 11779. 최소비용 구하기 2 / Python

https://www.acmicpc.net/problem/11779

알고리즘 설명

문제 설명

노드들이 주어지고 노드들 사이의 가중치가 주어졌을 때, 임의의 노드에서 다른 임의의 노드로 이동하는데 걸리는 최소 비용을 구하는 문제

코드 설명

다익스트라 알고리즘

우선순위 큐를 사용하여 최단 경로를 탐색한다.
주어진 시작점에서부터 시작하여 각 도시에 대한 최단 경로를 찾는다.
각 도시 now에서 인접한 도시 next로 가는 비용 tmp를 더한 값이 현재 저장된 최소 비용보다 작으면 갱신하고 큐에 추가한다.

dp[end][0] : 도착 도시까지의 최소 비용
len(dp[end][1]) : 경로에 포함된 도시의 개수
dp[end][1] : 최소 비용을 갖는 경로

from heapq import heappop, heappush # 최소비용의 값을 먼저 처리하기 위해 heqp 자료구조 사용
import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
arr = [[] for _ in range(n + 1)]
inf = float('inf')
dp = [[inf, [i]] for i in range(n + 1)]  # dp[i] = [최소 비용, 경로]

for _ in range(m):
    s, e, c = map(int, input().split())
    arr[s].append((e, c))

start, end = map(int, input().split())

def dijkstra(x):
    dp[x][0] = 0
    q = []
    heappush(q, (0, x))
    while q:
        cnt, now = heappop(q)
        if dp[now][0] < cnt:
            continue
        for next, tmp in arr[now]:
            if dp[next][0] > cnt + tmp:
                dp[next][0] = cnt + tmp
                dp[next][1] = dp[now][1] + [next]
                heappush(q, (cnt + tmp, next))

dijkstra(start)

print(dp[end][0])
print(len(dp[end][1]))
print(*dp[end][1])