概要

地点 \(1\) から地点 \(N\) への最短経路を、重み付き無向グラフ上で求める問題です。典型的な単一始点最短経路問題であり、ダイクストラ法を用いて解くことができます。

考察

問題の本質

この問題は、\(N\) 個の頂点と \(M\) 本の辺を持つ重み付き無向グラフにおいて、頂点 \(1\) から頂点 \(N\) への最短距離を求める問題です。辺の重み（所要時間）はすべて正（\(1 \leq C_i \leq 10^9\)）であることが制約から分かります。

素朴なアプローチとその問題点

• 全経路探索（DFS/BFS）: 地点 \(1\) から地点 \(N\) への全ての経路を列挙し、最小のものを選ぶ方法が考えられますが、経路数は指数的に増えるため、\(N\) や \(M\) が大きい場合にTLE（時間超過）になります。
• BFS（幅優先探索）: 重みなしグラフでは最短経路を求められますが、辺の重みが異なるため、単純なBFSでは正しい答えが得られずWAになります。

解決策

辺の重みがすべて非負であるため、ダイクストラ法が最適です。優先度付きキュー（最小ヒープ）を用いることで、効率よく最短距離を確定させていくことができます。

アルゴリズム

ダイクストラ法の手順は以下の通りです。

1. 初期化: 始点（地点 \(1\)）の距離を \(0\)、それ以外の地点の距離を \(\infty\) に設定する。優先度付きキューに \((0, 1)\)（距離, 地点番号）を入れる。

2. 繰り返し: キューが空になるまで以下を繰り返す。

   • キューから最小距離の要素 \((d, v)\) を取り出す。
   • もし \(d > \text{dist}[v]\) なら、すでにより短い経路で確定済みなのでスキップする（重要な枝刈り）。
   • 頂点 \(v\) に隣接する各頂点 \(u\) について、\(d + w\)（\(w\) は辺の重み）が現在の \(\text{dist}[u]\) より小さければ、\(\text{dist}[u]\) を更新し、\((d + w, u)\) をキューに追加する。

3. 結果: \(\text{dist}[N]\) が \(\infty\) のままなら到達不能なので -1 を出力。そうでなければ \(\text{dist}[N]\) を出力する。

具体例

例えば、\(N=3, M=3\) で以下の道路がある場合： - \(1 \to 2\)（所要時間 \(2\)）、\(2 \to 3\)（所要時間 \(3\)）、\(1 \to 3\)（所要時間 \(10\)）

ダイクストラ法は、まず地点 \(1\) から距離 \(0\) で開始し、地点 \(2\)（距離 \(2\)）と地点 \(3\)（距離 \(10\)）を発見します。次に地点 \(2\) を処理し、地点 \(3\) の距離が \(2 + 3 = 5 < 10\) と更新されます。最終的に答えは \(5\) となります。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • 各頂点・各辺について優先度付きキューへの操作（\(O(\log N)\)）が発生するため。
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リスト表現に \(O(N + M)\)、距離配列に \(O(N)\)、優先度付きキューに最大 \(O(M)\)。

実装のポイント

• 枝刈り（if d > dist[v]: continue）: キューから取り出した距離が既に確定した距離より大きい場合はスキップします。これがないと同じ頂点を何度も処理してしまい、大幅に遅くなります。

• 距離のオーバーフロー: \(C_i\) が最大 \(10^9\) で辺が最大 \(2 \times 10^5\) 本あるため、最短距離は最大で約 \(2 \times 10^{14}\) 程度になり得ます。Python は整数のオーバーフローがないため問題ありませんが、C++ などでは long long を使う必要があります。

• sys.stdin.readline の使用: Python では入力が遅くなりがちなため、sys.stdin.readline を使って高速化しています。

• 1-indexed の隣接リスト: 地点番号が \(1\) から \(N\) なので、サイズ \(N+1\) のリストを用意して添字をそのまま使えるようにしています。

  ソースコード

import heapq
import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b, c = map(int, sys.stdin.readline().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
    
    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[1] = 0
    pq = [(0, 1)]
    
    while pq:
        d, v = heapq.heappop(pq)
        if d > dist[v]:
            continue
        for u, w in graph[v]:
            nd = d + w
            if nd < dist[u]:
                dist[u] = nd
                heapq.heappush(pq, (nd, u))
    
    print(dist[N] if dist[N] != INF else -1)

main()

---

この解説は claude4.6opus-thinking によって生成されました。