概要

地点 \(1\) から地点 \(N\) まで所要時間 \(T\) 以下で到達できる経路のうち、通過する地点の危険度の最大値を最小化する問題です。「答えを二分探索 + 最短経路（ダイクストラ法）」で解きます。

考察

重要な気づき

この問題で求めたいのは「経路上の危険度の最大値の最小化」です。このような 「最大値を最小化する」 タイプの問題は、二分探索 と非常に相性が良いです。

ここで次のような判定問題を考えます。

危険度の上限を \(D\) に固定したとき、危険度 \(D\) 以下の地点だけを通って、所要時間 \(T\) 以下で地点 \(1\) から地点 \(N\) に到達できるか？

この判定問題には 単調性 があります。つまり、ある \(D\) で到達可能ならば、それより大きい \(D'\) (\(D' > D\)) でも必ず到達可能です。なぜなら、許される地点の集合が広がるだけで、使える経路が減ることはないからです。

逆に、ある \(D\) で到達不可能ならば、それより小さい \(D\) でも到達不可能です。

この単調性があるため、「到達可能になる最小の \(D\)」を二分探索で求めることができます。

危険度 \(D\) を固定したときの判定方法

危険度を \(D\) に固定すると、「危険度が \(D\) を超える地点は通れない」という制約になります。そこで、

• 危険度が \(D\) を超える地点を 使用禁止 にする
• 残った地点だけを使って、地点 \(1\) から地点 \(N\) への 最短時間 を求める

そして、その最短時間が \(T\) 以下なら「到達可能」と判定できます。これは典型的なダイクストラ法で求められます。

注意点として、出発地点 \(1\) と到着地点 \(N\) 自身も危険度の制約を受けます。\(P_1 > D\) または \(P_N > D\) の場合は、そもそも出発・到着できないので即座に到達不可能です。

素朴なアプローチの問題点

危険度の値は \(0 \le P_i \le 10^9\) と広い範囲を取り得るため、\(D\) を \(0\) から順に全探索したり、\(0\) から \(10^9\) まで値そのもので二分探索したりすると無駄が多くなります。

実は答えになり得る \(D\) の値は、いずれかの地点の危険度 \(P_i\) そのもの に限られます（最大値を取るので、必ずどこかの地点の危険度に一致します）。そこで、\(P_i\) の値を候補としてソート・重複除去し、その候補配列に対してインデックスで二分探索すれば効率的です。

アルゴリズム

1. すべての地点の危険度 \(P_i\) を集めてソートし、重複を除いて候補配列 cand を作る。
2. 候補配列のインデックスに対して二分探索を行う。
3. 各 \(D = \) cand[mid] に対して判定問題を解く:
   • \(P_1 > D\) または \(P_N > D\) なら不可能。
   • 危険度 \(D\) を超える地点を除いたグラフ上で、地点 \(1\) から地点 \(N\) への最短時間をダイクストラ法で計算する。
   • 最短時間が \(T\) 以下なら到達可能。
4. 到達可能になる最小の cand[mid] が答え。

二分探索では、「feasible(mid) が真なら答えを mid に更新して左側 (hi = mid - 1) を探索、偽なら右側 (lo = mid + 1) を探索」という典型的な「最小の真を探す」形になっています。

計算量

候補の個数は最大 \(N\) 個なので二分探索は \(O(\log N)\) 回。各回のダイクストラ法は \(O((N + M) \log N)\) です。

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

\(N \le 2 \times 10^4\), \(M \le 4 \times 10^4\) なので、十分高速に動作します。

実装のポイント

• オーバーフロー対策: \(W_j \le 10^9\) で、経路上で同じ道を複数回通る可能性もあり、距離の合計が大きくなり得ます。距離は long long で扱い、INF も LLONG_MAX / 4 のように加算してもオーバーフローしない値にしておきます。

• ダイクストラでの地点除外: 隣接頂点 \(v\) を緩和する際に if (P[v] > D) continue; とすることで、危険度 \(D\) を超える地点を自然に通行禁止にできます。出発・到着地点については関数の冒頭で別途チェックしています。

• 早期終了: ダイクストラ法では地点 \(N\) を最初に確定させた時点でその距離が確定最短距離なので、u == N で取り出したときに打ち切ると少し高速化できます（取り出した時点で dist[N] が確定しているため）。

• 候補の作成: sort の後 unique + erase で重複を除いておくことで、二分探索が正しく動作し、無駄な探索も減らせます。

  ソースコード

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

int main(){
    int N, M;
    long long T;
    scanf("%d %d %lld", &N, &M, &T);
    vector<long long> P(N+1);
    for(int i=1;i<=N;i++) scanf("%lld",&P[i]);
    
    vector<vector<pair<int,long long>>> g(N+1);
    for(int j=0;j<M;j++){
        int u,v; long long w;
        scanf("%d %d %lld",&u,&v,&w);
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    
    // candidate danger values
    vector<long long> cand(P.begin()+1, P.end());
    sort(cand.begin(), cand.end());
    cand.erase(unique(cand.begin(), cand.end()), cand.end());
    
    const long long INF = LLONG_MAX/4;
    vector<long long> dist(N+1);
    
    auto feasible = [&](long long D)->bool{
        if(P[1] > D || P[N] > D) return false;
        for(int i=1;i<=N;i++) dist[i]=INF;
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
        dist[1]=0;
        pq.push({0,1});
        while(!pq.empty()){
            auto [d,u]=pq.top(); pq.pop();
            if(d>dist[u]) continue;
            if(u==N){
                return dist[N] <= T;
            }
            for(auto [v,w]: g[u]){
                if(P[v] > D) continue;
                long long nd = d + w;
                if(nd < dist[v]){
                    dist[v]=nd;
                    pq.push({nd,v});
                }
            }
        }
        return dist[N] <= T;
    };
    
    // binary search smallest feasible candidate
    int lo=0, hi=(int)cand.size()-1, ans=hi;
    while(lo<=hi){
        int mid=(lo+hi)/2;
        if(feasible(cand[mid])){
            ans=mid;
            hi=mid-1;
        } else {
            lo=mid+1;
        }
    }
    
    printf("%lld\n", cand[ans]);
    return 0;
}

---

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