概要

速度規制で一部の道路の所要時間が \(2\) 倍になる状況で、地点 \(1\) から地点 \(N\) までの最短移動時間を求める問題です。到達不能なら \(-1\) を出力します。

考察

• この問題は「重み付き無向グラフの最短経路」です。
  各道路の重み（所要時間）が与えられ、規制対象の道路だけ重みが \(W_i \rightarrow 2W_i\) に変わるだけなので、最終的には「重みが確定したグラフ」に対して最短距離を求めればよいです。
• 素朴に「全経路を列挙して最短を探す」ことは不可能です。経路数は指数的に増え、\(N, M \le 2 \times 10^5\) では到底間に合いません。
• また、幅優先探索（BFS）は「全ての辺の重みが等しい」場合しか正しい最短距離を保証できません。本問は \(W_i\) が最大 \(10^9\) で辺ごとに異なるため、BFS では WA になります。
• 重みがすべて非負（\(W_i \ge 1\) なので \(2W_i\) も非負）であることから、標準的に ダイクストラ法 が使えます。

具体例として、ある道路の通常時間が \(5\) 分で規制対象なら、その道路だけ重みが \(10\) 分になります。こうして全道路の実際の重みを決めた後、最短経路問題として解けばよい、というのが本質です。

アルゴリズム

1. 入力で道路 \(i\) の情報 \((U_i, V_i, W_i)\) を保持する。
2. 規制対象の道路番号 \(C_1,\dots,C_K\) を boolean 配列 regulated に記録する（\(i\) 番道路が規制対象かどうか）。
3. 隣接リストを作る：
   • 道路 \(i\) の実際の重みを
     $\( w = \begin{cases} 2W_i & (\text{規制対象})\\ W_i & (\text{それ以外}) \end{cases} \)$ として、無向辺として g[U_i] と g[V_i] の両方に追加する。
4. ダイクストラ法で始点 \(1\) からの最短距離 dist を求める。
   • 優先度付きキュー（ヒープ）に (距離, 頂点) を入れて、最小距離の頂点から確定していく。
   • 取り出した (d,u) が古い情報（d != dist[u]）なら無視する。
5. dist[N] が更新されなければ到達不能なので \(-1\)、そうでなければ dist[N] を出力する。

計算量

• 時間計算量: \(O((N+M)\log N)\)
  （ダイクストラ法：各辺の緩和が最大 1 回ずつ有効に働き、ヒープ操作が \(\log N\)）
• 空間計算量: \(O(N+M)\)
  （隣接リスト、距離配列、ヒープ）

実装のポイント

• 入力が大きいため、sys.stdin.buffer.read() でまとめて読み、split() して高速に処理しています。

• 規制対象の道路番号は \(1\) 始まりなので、配列に合わせて -1 して \(0\) 始まりに直しています。

• 最短距離は最大で非常に大きくなり得ます（\(W_i \le 10^9\)、辺数も多い）ので、INF = 10**30 のように十分大きい値を使います。

• ダイクストラ法の定番として、ヒープから取り出した要素が古い場合を if d != dist[u]: continue で弾くことで、不要な探索を減らしています。

  ソースコード

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    idx = 0
    N, M, K = data[idx], data[idx + 1], data[idx + 2]
    idx += 3

    U = [0] * M
    V = [0] * M
    W = [0] * M
    for i in range(M):
        U[i] = data[idx]
        V[i] = data[idx + 1]
        W[i] = data[idx + 2]
        idx += 3

    regulated = [False] * M
    for _ in range(K):
        c = data[idx] - 1
        idx += 1
        regulated[c] = True

    g = [[] for _ in range(N + 1)]
    for i in range(M):
        w = W[i] * 2 if regulated[i] else W[i]
        u = U[i]
        v = V[i]
        g[u].append((v, w))
        g[v].append((u, w))

    INF = 10**30
    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:
            break
        for v, w in g[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))

    ans = dist[N]
    print(-1 if ans >= INF else ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。