概要

地点の危険度の最大値をできるだけ小さくしつつ、地点 \(1\) から地点 \(N\) まで所要時間 \(T\) 以下で到達できるかを考える問題です。

「危険度の上限」を決めると、その上限以下の地点だけを使って最短経路問題を解けばよいので、危険度に対して二分探索を行います。

考察

経路の危険度は、通った地点の危険度の最大値です。

例えば、ある値 \(X\) を決めて、

危険度が \(X\) 以下の地点だけを通って、地点 \(1\) から地点 \(N\) まで所要時間 \(T\) 以下で行けるか？

を判定できるとします。

この判定には単調性があります。

• 危険度上限 \(X\) で行けるなら、それより大きい \(Y \geq X\) でも行ける
• 危険度上限 \(X\) で行けないなら、それより小さい値でも行けない

なぜなら、上限を大きくすると使える地点が増えるだけで、減ることはないからです。

したがって、答えとなる最小の危険度を二分探索で求められます。

判定方法

危険度上限を limit とします。

このとき、通ってよい地点は \(P_i \leq \text{limit}\) を満たす地点だけです。

そのような地点だけを使って、地点 \(1\) から地点 \(N\) への最短時間を求めます。

各登山道の通過時間 \(W_j\) は正なので、最短経路はダイクストラ法で求められます。

最短時間が \(T\) 以下なら、その limit で到達可能です。

素朴な方法では厳しい理由

すべての経路を列挙することは、同じ地点や登山道を複数回通れるため不可能です。

また、危険度の候補を小さい順にすべて試し、そのたびにダイクストラ法を行うと、最大で \(N\) 回程度ダイクストラ法を実行することになり、制約上重くなります。

そこで、単調性を利用して二分探索することで、ダイクストラ法の実行回数を \(O(\log N)\) 回に抑えます。

アルゴリズム

まず、危険度の候補は各地点の危険度 \(P_i\) のいずれかです。

経路の危険度は「訪れた地点の危険度の最大値」なので、答えは必ずどこかの地点の危険度になります。

そのため、sorted(set(P)) によって危険度の候補を昇順に並べます。

ただし、経路には出発地点 \(1\) と到着地点 \(N\) が必ず含まれるため、答えは少なくとも

\[ \max(P_1, P_N) \]

以上です。

その位置から二分探索を開始します。

判定関数 feasible(limit) では、次を行います。

1. \(P_1 > \text{limit}\) または \(P_N > \text{limit}\) なら到達不可能
2. ダイクストラ法で地点 \(1\) からの最短時間を計算
3. ただし、危険度が limit を超える地点には移動しない
4. 地点 \(N\) に所要時間 \(T\) 以下で到達できれば True
5. そうでなければ False

ダイクストラ法中では、距離が \(T\) を超える経路は答えに不要なので、nd <= T の場合だけヒープに追加しています。

二分探索により、feasible(limit) が初めて True になる最小の limit を求めます。

計算量

危険度の異なる値の個数を \(K\) とします。\(K \leq N\) です。

1 回の判定ではダイクストラ法を行うため、

• \(O((N+M)\log N)\)

です。

これを二分探索で \(O(\log K)\) 回行うので、全体の計算量は以下です。

• 時間計算量: \(O((N+M)\log N \log K)\)
  ただし \(K \leq N\) なので、\(O((N+M)\log^2 N)\) と見てもよいです。
• 空間計算量: \(O(N+M)\)

実装のポイント

• グラフは無向なので、各辺を両方向に追加します。

• ダイクストラ法では、危険度が limit 以下の地点だけを遷移先にします。

• INF = T + 1 としています。今回は \(T\) 以下で到達できるかだけが重要なので、\(T\) を超える距離はすべて不要です。

• ヒープから取り出した距離が現在の dist[v] と違う場合は、古い情報なので無視します。

• 地点 \(N\) がヒープから取り出された時点で、最短距離が確定しているため、すぐ True を返せます。

• 辺の重みや \(T\) は最大 \(10^9\) と大きいので、他言語で実装する場合は long long 型を使う必要があります。

  ソースコード

import sys
import heapq
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    N = int(next(it))
    M = int(next(it))
    T = int(next(it))

    P = [int(next(it)) for _ in range(N)]
    adj = [[] for _ in range(N)]

    for _ in range(M):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        w = int(next(it))
        adj[u].append((v, w))
        adj[v].append((u, w))

    target = N - 1
    INF = T + 1

    def feasible(limit):
        if P[0] > limit or P[target] > limit:
            return False

        dist = [INF] * N
        dist[0] = 0
        hq = [(0, 0)]
        heappush = heapq.heappush
        heappop = heapq.heappop

        while hq:
            d, v = heappop(hq)
            if d != dist[v]:
                continue
            if v == target:
                return True

            for to, w in adj[v]:
                if P[to] <= limit:
                    nd = d + w
                    if nd <= T and nd < dist[to]:
                        dist[to] = nd
                        heappush(hq, (nd, to))

        return False

    vals = sorted(set(P))
    lo = bisect_left(vals, max(P[0], P[target]))
    hi = len(vals) - 1

    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(vals[mid]):
            hi = mid
        else:
            lo = mid + 1

    print(vals[lo])

if __name__ == "__main__":
    main()

---

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