概要

冠水地点を通ると追加コスト \(T\) がかかる街で、地点 \(1\) から地点 \(N\) までの「最短時間」を求めます。各移動は「道路の時間 + 到着地点が冠水なら \(T\)」として扱えば、通常の最短経路問題に帰着できます。

考察

重要な気づき

• 追加の時間ロス \(T\) は「冠水した地点を通過したとき」に発生します。
• 経路は「地点の列」として考えられるので、各移動で 次に到着する地点 が冠水していれば、その時点で \(T\) を足す、と整理できます。
• 出発地点 \(1\) も例外ではなく、冠水していれば最初から \(T\) がかかります（コードでは初期距離に反映）。

つまり、辺 \((u \to v)\) を移動するコストは - \(w(u,v) + (v\ \text{が冠水なら}\ T\ \text{else}\ 0)\) となり、すべて非負なのでダイクストラ法が使えます。

素朴なアプローチがダメな理由

• 全経路を列挙して最小を取るのは、経路数が指数的に増えるため不可能です。
• BFS は辺の重みが一定でない（\(w_i\) が様々、さらに \(T\) も加算）ので最短路を保証できません。
• \(N, M \le 2\times 10^5\) なので、最短路は \(O((N+M)\log N)\) 程度で解く必要があります。

どう解決するか

• 「道路の重み」に「到着地点の冠水ペナルティ」を加えた新しい重みで考え、通常の最短経路として ダイクストラ法 で解きます。

アルゴリズム

1. 隣接リストでグラフを構築する（各道路は双方向）。
2. 冠水地点を boolean 配列 flooded[v] として保持する。
3. ダイクストラ法を実行する。
   • 初期値：dist[1] = (1が冠水なら T else 0)
   • 優先度付きキューから (現在距離, 頂点) を取り出す。
   • 辺 \((u, v, w)\) に対し、次の候補距離を $\( nd = dist[u] + w + (flooded[v] ? T : 0) \)$ として更新する。
4. dist[N] が答え。

具体例イメージ

例えば \(1 \to 3\) を通って \(3\) が冠水なら、「道路時間 \(w(1,3)\) に加えて \(T\)」がその移動で上乗せされます。次に \(3 \to 5\) で \(5\) が冠水なら、さらにその移動で \(T\) が上乗せされます。
このように「到着ごとに課金」と考えると、単純に足し算で最短路計算できます。

計算量

• 時間計算量: \(O((N+M)\log N)\)（ダイクストラ法＋優先度付きキュー）
• 空間計算量: \(O(N+M)\)（隣接リスト、距離配列、冠水配列など）

実装のポイント

• 冠水ペナルティは「到着地点」に足す：nd = d + w + (T if flooded[v] else 0) とするのが自然で、数え漏れが起きにくいです。

• 出発地点の扱い：地点 \(1\) が冠水している場合も \(T\) がかかるので、dist[1] を最初から \(T\) にします。

• ヒープから取り出した値の無効化チェック：if d != dist[u]: continue を入れることで、古い情報での探索を防ぎます。

• 入力が大きいため、sys.stdin.buffer.read() で高速に読み取っています。

• 距離は最大で非常に大きくなりうるため、INF = 10**30 のように十分大きい値を使います。

  ソースコード

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    idx = 0

    N, M, K, T = data[idx], data[idx + 1], data[idx + 2], data[idx + 3]
    idx += 4

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, w = data[idx], data[idx + 1], data[idx + 2]
        idx += 3
        adj[u].append((v, w))
        adj[v].append((u, w))

    flooded = [False] * (N + 1)
    for _ in range(K):
        g = data[idx]
        idx += 1
        flooded[g] = True

    INF = 10**30
    dist = [INF] * (N + 1)
    dist[1] = T if flooded[1] else 0

    hq = [(dist[1], 1)]
    while hq:
        d, u = heapq.heappop(hq)
        if d != dist[u]:
            continue
        if u == N:
            break
        for v, w in adj[u]:
            nd = d + w + (T if flooded[v] else 0)
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(hq, (nd, v))

    print(dist[N])

if __name__ == "__main__":
    main()

---

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