令和6年度春期応用技術者試験_午後_問3

r06h_ap_pm3_3.py

import heapq


def distance():
    N = 5  # ノードの個数
    INF = float("inf")  # 十分大きい定数
    # edge[m, n]には、ノードmからノードnへの距離を格納
    # 二つのノードが隣接していない場合には INF を格納
    edge = [
        [INF, 10, 16, INF, INF],
        [10, INF, 4, 3, INF],
        [16, 4, INF, 2, 3],
        [INF, 3, 2, INF, 6],
        [INF, INF, 3, 6, INF],
    ]
    GOAL = N - 1  # 終点のノード番号
    dist = [INF] * N  # 始点ノード距離。初期値はINF。
    viaNode = [-1] * N  # 最短経路のノード番号を格納する
    dist[0] = 0
    que = []
    heapq.heappush(que, (dist[0], 0))
    while que:
        curNode = heapq.heappop(que)[1]
        if curNode == GOAL:
            j = GOAL  # 終点のノード番号
            print(GOAL)  # 終点のノード番号の出力
            while j > 0:  # 最短経路の出力
                print(viaNode[j])
                j = viaNode[j]
            return dist[curNode]
        for k in range(N):
            if dist[curNode] + edge[curNode][k] < dist[k]:
                dist[k] = dist[curNode] + edge[curNode][k]
                heapq.heappush(que, (dist[k], k))
                viaNode[k] = curNode


print(distance())