< 桜木凛さんのAI生成コード置き場

ダイクストラ法テンプレ

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

import heapq

# INF は十分大きな値（1 << 60 は約 10^18 です）
INF = 1 << 60
dist = [INF] * N

# 1. スタート地点（頂点 0）の初期設定
dist[0] = (★スタート地点の初期コスト)
pq = [(dist[0], 0)]  # (コスト, 頂点番号) のタプルを入れます

while pq:
    # 2. 今一番コストが小さい頂点を取り出す
    d, u = heapq.heappop(pq)

    # 3. 古い情報のスキップ（とても大事です！）
    if d > dist[u]:
        continue

    # 4. 隣の頂点 v と、その間の辺の重み b を順番に見る
    for v, b in G[u]:
        nd = dist[u] + (★u から v へ移動する追加コスト)
        if nd < dist[v]:
            dist[v] = nd
            heapq.heappush(pq, (nd, v))