概要

辺の重みが一部変更された無向グラフにおいて、頂点 \(1\) から頂点 \(N\) までの最短経路（最短時間）を求める問題です。

考察

この問題は、各地点を「頂点」、道路を「辺」、所要時間を「辺の重み」とした重み付き無向グラフ上の最短経路問題に帰着できます。

辺の重みがすべて \(0\) 以上であるため、ダイクストラ法（Dijkstra’s Algorithm） を使うのが最適です。 もし全ての経路の組み合わせを探索するような素朴な深さ優先探索（DFS）を行うと、計算量が指数関数的に増大し、TLE（実行時間制限超過）になってしまいます。また、ベルマンフォード法を使っても \(O(NM)\) の時間がかかり、今回の制約（\(N, M \le 2 \times 10^5\)）では TLE となります。

速度規制による所要時間の増加については、グラフを構築する段階で対処できます。あらかじめ速度規制の対象となる道路番号を集合（Set）などで持っておき、辺の情報を隣接リストに登録する際に、その道路が規制対象であれば重みを \(2\) 倍にして登録すればよいだけです。

アルゴリズム

1. 入力の受け取りと前処理:
   • 速度規制の対象となっている道路の番号 \(C_1, C_2, \ldots, C_K\) を、高速に検索できるようにハッシュセット（Set）に格納します。
2. グラフの構築:
   • 各頂点から繋がる辺を管理する「隣接リスト」を作成します。
   • 道路 \(i\) を隣接リストに追加する際、道路番号 \(i\) が先ほどのセットに含まれていれば所要時間を \(2W_i\) とし、含まれていなければ \(W_i\) として、双方向に辺を張ります。
3. ダイクストラ法の実行:
   • 頂点 \(1\) から各頂点への最短距離を管理する配列 dist を用意し、初期値を無限大（\(\infty\)）に、dist[1] を \(0\) に設定します。
   • 優先度付きキュー（ヒープ）に (距離 0, 頂点 1) を入れます。
   • キューから「現在わかっている距離が最も短い頂点 \(u\)」を取り出し、その頂点から繋がる各頂点 \(v\) に対して、頂点 u までの距離 + 辺の重み が現在の dist[v] より小さければ、dist[v] を更新してキューに (新しい距離, 頂点 v) を追加します。
   • これをキューが空になるか、目的の頂点 \(N\) への最短距離が確定するまで繰り返します。
4. 答えの出力:
   • dist[N] が無限大のままであれば到達できないため -1 を、そうでなければ dist[N] を出力します。

計算量

• 時間計算量: \(O(M \log M)\) または \(O(M \log N)\)
  • グラフの構築に \(O(M)\)、速度規制のセット構築に \(O(K)\) かかります。
  • ダイクストラ法では、優先度付きキューへの追加・取り出しが最大で辺の数 \(M\) 回行われるため、\(O(M \log M)\) の時間がかかります。
  • 全体として \(O(M \log M)\) となり、制約下でも十分に高速に動作します。
• 空間計算量: \(O(N + M)\)
  • 頂点数 \(N\) と辺の数 \(M\) に比例するサイズの隣接リストと、距離配列、優先度付きキューを保持するためのメモリが必要です。

実装のポイント

• 無限大（INF）の設定: 制約より、所要時間の最大値は \(10^9\) であり、最大で \(N-1\) 本の辺を通る可能性があります。したがって、最短経路の長さは最大で \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) 程度になる可能性があります。そのため、距離の初期値として設定する無限大の値は、これより十分に大きい \(10^{18}\) などに設定する必要があります。

• 高速な入出力: 入力されるデータ量が多いため、Pythonの場合は sys.stdin.read().split() を用いて入力を一括で読み込むことで、実行時間を大幅に短縮できます。

• 不要な探索のスキップ: ダイクストラ法のループ内でキューから取り出した距離 d が、すでに記録されている dist[u] より大きい場合、それは古い（最適ではない）情報なので continue でスキップすることが重要です。これにより無駄な計算を防ぎます。

  ソースコード

import sys
import heapq

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    idx = 3
    U = [0] * (M + 1)
    V = [0] * (M + 1)
    W = [0] * (M + 1)
    for i in range(1, M + 1):
        U[i] = int(input_data[idx])
        V[i] = int(input_data[idx+1])
        W[i] = int(input_data[idx+2])
        idx += 3
        
    restricted = set()
    if K > 0:
        for _ in range(K):
            restricted.add(int(input_data[idx]))
            idx += 1
            
    adj = [[] for _ in range(N + 1)]
    for i in range(1, M + 1):
        u = U[i]
        v = V[i]
        w = W[i]
        if i in restricted:
            w *= 2
        adj[u].append((v, w))
        adj[v].append((u, w))
        
    INF = 10**18
    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 adj[u]:
            if dist[v] > d + w:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
                
    if dist[N] == INF:
        print(-1)
    else:
        print(dist[N])

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。