[Python]標準/ゴールド/1779:最低コスト2

質問リンク:https://www.acmicpc.net/problem/11779
マルチアウトプットアルゴリズムの問題.この問題は最短距離だけでなく,最短経路も要求される.これは私が初めてパスを解いたので、ドエストラアルゴリズムの流れを正しく理解すれば、難しくありません.マルチアウトレットは、優先キューにノードを挿入して最短距離を更新するアルゴリズムであるため、そのキューにパスを格納してアルゴリズムを実行するだけでよい.
覚えておいてください.
最短パスを求める場合は、キューにパス挿入を追加するだけです.

Pythonコード

import sys
import heapq
INF = 987654321
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    # 출발 노드, 도착 노드, 비용
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))


def dijkstra(start, end):
    # [거리, 지나온 경로]
    distance = [[INF, []] for _ in range(N + 1)]
    distance[start] = [0, [start]]

    q = []
    # (거리, 노드, 지나온 경로)
    heapq.heappush(q, (0, start, [start]))

    while q:
        dist, now, path = heapq.heappop(q)
        if distance[now][0] < dist:
            continue

        for node, d in graph[now]:
            cost = dist + d

            if cost < distance[node][0]:
                distance[node][0] = cost
                distance[node][1] = path + [node]
                q.append((cost, node, path + [node]))

    print(distance[end][0])
    print(len(distance[end][1]))
    for x in distance[end][1]:
        print(x, end=' ')


S, E = map(int, sys.stdin.readline().split())
dijkstra(S, E)