概要

地点 \(1\) から地点 \(N\) への最短経路問題です。一方通行の道路で構成された重み付きグラフにおいて、ダイクストラ法を用いて最短時間を求めます。

考察

問題の整理

• \(N\) 個の地点と \(M\) 本の一方通行道路がある
• 各道路には移動時間（コスト）が設定されている
• 地点 \(1\) から地点 \(N\) への最短時間を求めたい

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

全探索（DFS/BFS） で全ての経路を試すと、経路数が指数的に増加し、\(N\) や \(M\) が大きい場合にTLE（時間超過）になります。

例えば、完全グラフに近い場合、経路数は \(O(N!)\) にもなり得ます。

解決策

ダイクストラ法 を使います。このアルゴリズムは、辺の重みが非負である単一始点最短経路問題を効率的に解くことができます。

今回の問題では \(C_i \geq 1\) なので、辺の重みは全て正であり、ダイクストラ法が適用可能です。

アルゴリズム

ダイクストラ法は以下の手順で動作します：

1. 初期化: 始点（地点 \(1\)）の距離を \(0\)、他の全ての地点の距離を \(\infty\) に設定
2. 優先度付きキュー: 距離が最小の頂点を効率的に取り出すために使用
3. 繰り返し処理:
   • キューから距離最小の頂点 \(u\) を取り出す
   • \(u\) から出ている各辺 \((u, v)\) について、\(v\) への距離を更新できるか確認
   • 更新できれば、新しい距離をキューに追加

例: N=4, 道路: (1→2, 時間3), (1→3, 時間5), (2→4, 時間2), (3→4, 時間1)

初期状態: dist = [∞, 0, ∞, ∞, ∞]  (index 0は未使用)

手順1: 頂点1を処理 → dist[2]=3, dist[3]=5
手順2: 頂点2を処理 → dist[4]=3+2=5
手順3: 頂点3を処理 → dist[4]=min(5, 5+1)=5 (更新なし)

答え: dist[4] = 5

計算量

• 時間計算量: \(O((N + M) \log N)\)

  • 各頂点は優先度付きキューから最大1回取り出される
  • 各辺は最大1回緩和処理される
  • ヒープ操作は \(O(\log N)\)

• 空間計算量: \(O(N + M)\)

  • グラフの隣接リスト: \(O(M)\)
  • 距離配列: \(O(N)\)
  • 優先度付きキュー: 最大 \(O(M)\)（重複がある場合）

実装のポイント

1. スキップ処理: if d > dist[u]: continue

   • 同じ頂点が異なる距離でキューに複数回追加されることがある
   • 既により短い距離で処理済みの場合はスキップすることで無駄な計算を省く

2. 早期終了: if u == N: return

   • ゴール地点が確定したら即座に終了できる（ダイクストラ法の性質上、最初にキューから取り出された時点で最短距離が確定）

3. 距離の型: \(C_i\) が最大 \(10^9\)、辺が最大 \(2 \times 10^5\) 本なので、最短距離は最大 \(2 \times 10^{14}\) 程度

   • Pythonでは整数オーバーフローの心配はないが、他の言語では64bit整数型を使用する

4. defaultdictの使用: 存在しない頂点へのアクセス時にエラーを防ぎ、コードを簡潔に書ける

   ソースコード

import heapq
import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    
    # 隣接リストでグラフを構築
    graph = defaultdict(list)
    for _ in range(M):
        u, v, c = map(int, input().split())
        graph[u].append((v, c))
    
    # ダイクストラ法
    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[1] = 0
    
    # (距離, 頂点)
    pq = [(0, 1)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        # すでにより短い経路が見つかっている場合はスキップ
        if d > dist[u]:
            continue
        
        # ゴールに到達したら終了
        if u == N:
            print(dist[N])
            return
        
        for v, cost in graph[u]:
            new_dist = d + cost
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
    
    print(dist[N])

solve()

---

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