概要

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

「危険度の上限」を決めると、その危険度以下の地点だけを使って最短経路を求めればよいので、二分探索とダイクストラ法を組み合わせて解きます。

考察

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

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

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

を考えます。

これは、危険度が \(X\) を超える地点を使えないものとしてグラフから除外し、残った地点だけで最短経路を求める問題になります。

重要な単調性

ある危険度上限 \(X\) で到達可能なら、より大きい上限 \(Y \ge X\) でも到達可能です。

なぜなら、\(Y\) の方が使える地点が増えるだけで、使える経路が減ることはないからです。

つまり、判定結果は次のように単調になります。

危険度上限: 小さい -------------------- 大きい
判定結果:   false false false true true true

このような単調性があるので、答えを二分探索できます。

答えの候補

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

したがって、答えは必ずどれかの地点の危険度 \(P_i\) になります。

そのため、\(0\) から \(10^9\) の範囲をそのまま二分探索してもよいですが、この実装では \(P_i\) の値を集めて重複を除いた配列 vals に対して二分探索しています。

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

すべての経路を列挙して、その中から所要時間 \(T\) 以下のものを探す方法は、経路数が非常に多くなるため不可能です。

また、各危険度候補について毎回ダイクストラ法を行うと、候補数は最大で \(N\) 個あるため、

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

程度かかり、制約上厳しいです。

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

アルゴリズム

まず、各地点の危険度 \(P_i\) を集め、昇順にソートして重複を除いた配列 vals を作ります。

次に、次の判定関数 ok(lim) を考えます。

判定関数 ok(lim)

lim を危険度の上限とします。

• 危険度が lim を超える地点は使えない
• 使える地点だけを通って、地点 \(1\) から地点 \(N\) まで所要時間 \(T\) 以下で行けるかを判定する

具体的には、以下のようにします。

1. もし出発地点 \(1\) または到着地点 \(N\) の危険度が lim を超えていたら、必ず不可能なので false
2. ダイクストラ法で、地点 \(1\) から各地点への最短時間を求める
3. 辺をたどるとき、移動先の地点の危険度が lim を超えていたら無視する
4. 地点 \(N\) への最短時間が \(T\) 以下なら true

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

二分探索

vals に対して、「ok(vals[i]) が初めて true になる位置」を二分探索します。

vals[i] が小さいほど条件は厳しい
vals[i] が大きいほど条件は緩い

よって、条件を満たす最小の vals[i] が答えです。

計算量

危険度の種類数を \(K\) とします。\(K \le N\) です。

• ダイクストラ法 1 回あたり: \(O((N+M)\log N)\)
• 二分探索の回数: \(O(\log K)\)

したがって、

• 時間計算量: \(O((N+M)\log N \log N)\)
• 空間計算量: \(O(N+M)\)

実装のポイント

• 距離や時間、危険度は最大で \(10^9\) なので、合計時間は int に収まらない可能性があります。long long を使います。

• ok(lim) の中では、危険度が lim を超える地点には遷移しません。

• ダイクストラ法中に距離がすでに \(T\) を超えている場合、その先へ進んでも時間は増えるだけなので無視できます。

• 地点番号は入力では \(1\) 始まりですが、実装では \(0\) 始まりに直しています。

• 同じ2地点を結ぶ登山道が複数あっても、隣接リストにそのまま追加して問題ありません。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long T;
    cin >> N >> M >> T;

    vector<long long> P(N);
    for (int i = 0; i < N; i++) cin >> P[i];

    vector<vector<pair<int, long long>>> g(N);
    for (int i = 0; i < M; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        --u; --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    vector<long long> vals = P;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    auto ok = [&](long long lim) -> bool {
        if (P[0] > lim || P[N - 1] > lim) return false;

        const long long INF = (1LL << 62);
        vector<long long> dist(N, INF);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

        dist[0] = 0;
        pq.push({0, 0});

        while (!pq.empty()) {
            auto [d, v] = pq.top();
            pq.pop();

            if (d != dist[v]) continue;
            if (d > T) continue;
            if (v == N - 1) return d <= T;

            for (auto [to, w] : g[v]) {
                if (P[to] > lim) continue;
                long long nd = d + w;
                if (nd < dist[to] && nd <= T) {
                    dist[to] = nd;
                    pq.push({nd, to});
                }
            }
        }

        return false;
    };

    int ng = -1, ok_idx = (int)vals.size() - 1;
    while (ok_idx - ng > 1) {
        int mid = (ng + ok_idx) / 2;
        if (ok(vals[mid])) ok_idx = mid;
        else ng = mid;
    }

    cout << vals[ok_idx] << '\n';
    return 0;
}

---

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