概要

速度規制のある道路の所要時間を2倍に変更した上で、地点 \(1\) から地点 \(N\) への最短経路を求める問題です。典型的な重み付きグラフの最短経路問題であり、ダイクストラ法で解くことができます。

考察

問題の整理

• \(N\) 個の地点と \(M\) 本の双方向道路からなるグラフが与えられる
• \(K\) 本の道路は速度規制を受けており、所要時間が通常の 2倍 になる
• 地点 \(1\) から地点 \(N\) への最短時間を求める

重要な気づき

この問題では、速度規制によって辺の重みが変わるだけで、グラフの構造自体は変わりません。つまり、辺の重みを適切に設定してから、通常の最短経路問題を解けばよい ということになります。

具体的には、道路 \(i\) の重みを次のように設定します：

• 道路 \(i\) が速度規制対象（\(i \in \{C_1, C_2, \ldots, C_K\}\)）なら、重みは \(2W_i\)
• そうでなければ、重みは \(W_i\)

なぜダイクストラ法か

辺の重みはすべて正（\(W_i \geq 1\) なので \(2W_i\) も正）であるため、ダイクストラ法が適用できます。BFS は重みなしグラフ向けなので使えません。ベルマン–フォード法でも正しい答えは得られますが、計算量が \(O(NM)\) となり、\(N, M\) が最大 \(2 \times 10^5\) の場合は間に合わない可能性があります。

アルゴリズム

1. 入力を読み取り、各道路の情報を保存する
2. 速度規制対象の道路番号を集合（set）に格納する
3. 隣接リストを構築する。各道路について、速度規制対象なら重み \(2W_i\)、そうでなければ重み \(W_i\) として辺を追加する
4. ダイクストラ法で地点 \(1\) から各地点への最短距離を求める
   • 優先度付きキュー（最小ヒープ）を使い、距離が最小の頂点から順に確定させる
   • 地点 \(N\) に到達した時点で早期終了できる（最適化）
5. 地点 \(N\) への最短距離を出力する。到達不可能なら \(-1\) を出力する

具体例

例えば、\(N=3, M=3\) で以下の道路があるとします： - 道路1: 地点1–2、所要時間 \(3\) - 道路2: 地点2–3、所要時間 \(5\) - 道路3: 地点1–3、所要時間 \(10\)

速度規制対象が道路3（\(K=1, C_1=3\)）の場合、道路3の所要時間は \(20\) になります。すると、地点1→地点2→地点3のルート（所要時間 \(3+5=8\)）が最短となります。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • ダイクストラ法の標準的な計算量です。各辺について最大1回のヒープ操作（\(O(\log N)\)）を行います。
• 空間計算量: \(O(N + M)\)
  • 隣接リスト、距離配列、優先度付きキューの分です。

実装のポイント

• 速度規制の判定を高速に行う: 速度規制対象の道路番号を set に格納することで、\(O(1)\) で判定できます。リストの線形探索（\(O(K)\)）を毎回行うと遅くなります。

• 入力の高速読み取り: \(N, M\) が大きいため、Python では sys.stdin.buffer.read() でまとめて読み取ることで入力処理を高速化しています。

• 早期終了: ダイクストラ法で地点 \(N\) をヒープから取り出した時点で、その距離が最短であることが保証されるため、即座に答えを出力して終了できます。

• \(K = 0\) の場合: 速度規制対象の道路がない場合、最終行の入力が存在しない点に注意が必要です（コード中では if K > 0 で分岐）。

  ソースコード

import heapq
import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    edges = []
    for i in range(M):
        U = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        W = int(input_data[idx]); idx += 1
        edges.append((U, V, W))
    
    restricted = set()
    if K > 0:
        for j in range(K):
            C = int(input_data[idx]); idx += 1
            restricted.add(C)
    
    # Build adjacency list
    adj = [[] for _ in range(N + 1)]
    for i in range(M):
        U, V, W = edges[i]
        road_id = i + 1
        if road_id in restricted:
            w = 2 * W
        else:
            w = W
        adj[U].append((V, w))
        adj[V].append((U, w))
    
    # Dijkstra
    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(d)
            return
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    
    print(-1 if dist[N] == INF else dist[N])

main()

---

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