概要

この問題は、重み付き無向グラフにおいて、特定の頂点を通る際に追加コストが発生する条件下での最短経路を求める問題です。

考察

この問題は基本的には最短経路探索の問題ですが、いくつかの重要なポイントがあります。

まず、冠水している地点に立ち寄ると、その時点で追加で時間 \(T\) のロスが発生します。これは「辺の重み」ではなく、「頂点に到達した瞬間」に発生するコストです。つまり、ダイクストラ法で最短距離を管理するときに、単に辺のコストだけでなく、訪問先の頂点が冠水しているかどうかを考慮する必要があります。

また、出発地点（頂点 \(1\)）や目的地（頂点 \(N\)）が冠水している場合も、同様に時間ロスが発生することに注意が必要です。特に、出発時にすでに冠水していれば、初期コストとして \(T\) を加算しなければなりません。

素朴な方法（例えば全探索やDFSなど）では、頂点数 \(N\) が最大 \(2 \times 10^5\) であるため、現実的な時間内に解くことができません。そこで、効率的に最短経路を求めるためのアルゴリズムであるダイクストラ法を使用します。

ダイクストラ法では、優先度付きキュー（ヒープ）を使って、最もコストの低い頂点から順に処理していくことで、各頂点への最短距離を効率的に求めることができます。

アルゴリズム

この問題では、以下のようにダイクストラ法を拡張して使用します。

1. グラフの構築

   • 各道路を双方向の辺として隣接リスト adj に格納します。各辺は (隣接頂点, 辺の重み) の形で保存します。

2. 冠水地点の管理

   • 冠水している頂点を集合 flooded で管理し、ある頂点が冠水しているかを高速に判定できるようにします。

3. ダイクストラ法の初期化

   • 頂点 \(1\) から各頂点への最短距離を記録する配列 dist を用意し、初期値は \(\infty\) に設定します。
   • 頂点 \(1\) が冠水していれば、初期コストは \(T\)、そうでなければ \(0\) とします。
   • 優先度付きキューに (コスト, 頂点番号) の形で初期状態を追加します。

4. ダイクストラ法のメインループ

   • キューから最もコストの低い頂点を取り出し、それが現在の最短距離よりも大きい場合はスキップします。
   • 頂点が目的地 \(N\) であれば、その時点でのコストが答えなので、出力して終了します。
   • それ以外の場合は、隣接する各頂点に対して新しいコストを計算します：
     • 移動コストは 現在のコスト + 辺の重み + (移動先が冠水していれば T)
     • この新しいコストが既存の最短距離より小さければ更新し、キューに追加します。

このようにして、頂点ごとの追加コストを考慮しながら最短経路を求めることができます。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • ダイクストラ法の標準的な計算量です。各辺を最大1回ずつ処理し、優先度付きキューの操作が \(\log N\) かかります。
• 空間計算量: \(O(N + M)\)
  • 隣接リスト、距離配列、冠水地点の集合などで使用されるメモリです。

実装のポイント

• 冠水しているかどうかの判定は set を使うことで \(O(1)\) で行えるようにする。
• ダイクストラ法では、同じ頂点でも異なるコストでキューに入る可能性があるため、取り出したコストが現在の最短距離より大きければスキップする処理が必須。
• 出発地点や目的地が冠水している場合の処理を忘れずに。

## ソースコード

```python
import heapq
import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        adj[u].append((v, w))
        adj[v].append((u, w))
    
    flooded = set()
    if K > 0:
        for _ in range(K):
            g = int(data[idx]); idx += 1
            flooded.add(g)
    
    # ダイクストラ法
    # 頂点番号、コスト
    dist = [float('inf')] * (N+1)
    dist[1] = T if 1 in flooded else 0
    pq = [(dist[1], 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]:
            cost_add = w + (T if v in flooded else 0)
            new_dist = d + cost_add
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。