概要

冠水している地点を通ると追加の時間ロスが発生するグラフ上で、地点 \(1\) から地点 \(N\) への最短経路を求める問題です。基本的なダイクストラ法を、冠水地点のペナルティを考慮して適用すれば解けます。

考察

問題の本質を読み解く

この問題は重み付きグラフの最短経路問題ですが、辺のコストだけでなく、頂点を通過するコストも存在する点が通常と異なります。

具体的には： - 辺 \((u, v)\) を通るとき、辺の重み \(w\) がかかる - さらに、到着先の頂点 \(v\) が冠水していれば追加で \(T\) の時間ロスが発生する - 出発地点 \(1\) が冠水している場合も、最初に \(T\) の時間ロスが発生する

頂点コストを辺コストに変換する考え方

頂点にコストがある問題は、頂点に入るときのコストを、その頂点に向かう辺のコストに加算することで、通常の辺コストのみの最短経路問題に帰着できます。

例えば、頂点 \(v\) が冠水している場合、\(v\) に向かうすべての辺のコストに \(T\) を加算すると考えます。出発地点 \(1\) については、初期コストとして \(T\)（冠水していれば）を設定します。

具体例

地点が \(1, 2, 3\) の3つで、辺が \((1, 2, 5)\) と \((2, 3, 3)\)、地点 \(2\) が冠水（\(T = 10\)）の場合：

• 地点 \(1\) → 地点 \(2\)：辺コスト \(5\) ＋ 冠水コスト \(10\) ＝ \(15\)
• 地点 \(2\) → 地点 \(3\)：辺コスト \(3\) ＋ 冠水コスト \(0\) ＝ \(3\)
• 合計：\(15 + 3 = 18\)

アルゴリズム

1. 入力を読み込み、隣接リストでグラフを構築する
2. 冠水地点の集合を作成する（\(O(1)\) で判定できるようにセットを使う）
3. ダイクストラ法を以下のように実行する：
   • 初期コスト：地点 \(1\) が冠水していれば \(T\)、そうでなければ \(0\)
   • 辺 \((u, v, w)\) を使って \(v\) に移動するとき、コストは \(w + (\)地点 \(v\) が冠水なら \(T\)、そうでなければ \(0)\)
   • 優先度付きキュー（最小ヒープ）を用いて、各頂点への最短距離を更新していく
4. \(dist[N]\) を出力する

これは通常のダイクストラ法そのものであり、辺の重みに頂点の冠水コストを加えただけです。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • ダイクストラ法の標準的な計算量です。各辺について最大1回のヒープ操作（\(O(\log N)\)）が行われます。
• 空間計算量: \(O(N + M)\)
  • 隣接リスト、距離配列、冠水地点の集合に必要な領域です。

実装のポイント

• 冠水地点の判定にセット（set）を使う：リストで線形探索すると遅くなるため、\(O(1)\) で判定できるセットを使います。

• 出発地点の冠水処理を忘れない：地点 \(1\) が冠水している場合、初期距離を \(T\) に設定する必要があります。これを忘れると WA になります。

• \(K = 0\) のときの入力処理：冠水地点が \(0\) 個の場合、冠水地点の行が与えられないため、入力の読み取りに注意が必要です。

• オーバーフローに注意：辺の重み \(w\) と \(T\) が最大 \(10^9\) で、経路が長くなると合計が大きくなりますが、Python では整数のオーバーフローがないため問題ありません（C++ 等では long long を使う必要があります）。

  ソースコード

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
    T = int(input_data[idx]); idx += 1
    
    adj = [[] for _ in range(N + 1)]
    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
        adj[u].append((v, w))
        adj[v].append((u, w))
    
    flooded = set()
    if K > 0:
        for j in range(K):
            g = int(input_data[idx]); idx += 1
            flooded.add(g)
    
    # Dijkstra from node 1 to node N
    # When visiting a node that is flooded, add T to the cost
    INF = float('inf')
    dist = [INF] * (N + 1)
    
    start_cost = T if 1 in flooded else 0
    dist[1] = start_cost
    
    pq = [(start_cost, 1)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        if u == N:
            break
        for v, w in adj[u]:
            extra = T if v in flooded else 0
            nd = d + w + extra
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    
    print(dist[N])

main()

---

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