概要

頂点 \(1\) から頂点 \(N\) まで、所要時間 \(T\) 以下で到達できる経路の中で、経路上の頂点の危険度の最大値を最小化する問題です。

考察

この問題は「最大化された最小値」を求めるという典型的な構造をしています。このような問題では、二分探索を用いるのが有効です。

具体的には、「経路の危険度の最大値を \(K\) 以下にできるか？」という判定問題を考えることで、\(K\) を二分探索によって絞り込むことができます。 \(K\) が決まったとき、判定問題は「危険度が \(K\) を超える地点を通らずに、頂点 \(1\) から頂点 \(N\) までの所要時間が \(T\) 以下で到達できるか？」という問題に帰着します。これは、移動できない地点を除いたグラフ上で最短経路を求めることで判定できます。

すべての可能な \(K\) について愚直に最短経路を求めると、計算量が大きくなりTLE（時間超過）になります。しかし、二分探索を用いることで判定回数を大幅に減らすことができ、制限時間内に正解することができます。

アルゴリズム

1. 答えの候補を準備する: 各地点の危険度 \(P_i\) を集め、重複を排除してソートした配列 vals を作成します。この配列上で二分探索を行います。
2. 二分探索: 探索範囲の中央のインデックス mid を選び、最大許容危険度 \(K = \text{vals[mid]}\) とします。
3. 判定（ダイクストラ法）:
   • もし始点（地点 \(1\)）または終点（地点 \(N\)）の危険度が \(K\) を超えている場合、この \(K\) では到達不可能なため、探索範囲の下限を mid + 1 に上げます。
   • それ以外の場合、ダイクストラ法を用いて頂点 \(1\) から頂点 \(N\) への最短時間を求めます。ただし、移動先の頂点の危険度が \(K\) を超える場合はその道を通らないようにします。
   • 求めた最短時間が \(T\) 以下であれば、その \(K\) は条件を満たすため、より小さい \(K\) が存在する可能性があります。したがって、探索範囲の上限を mid に下げます。
   • 最短時間が \(T\) を超える場合は条件を満たさないため、探索範囲の下限を mid + 1 に上げます。
4. 出力: 二分探索が終了した時点での vals[l] が答えとなります。

計算量

• 時間計算量: 危険度の値の種類数を \(O(N)\) とすると、二分探索の反復回数は \(O(\log N)\) 回です。各反復でダイクストラ法を実行するため \(O(M \log N)\) の時間がかかります。したがって全体の時間計算量は \(O(M \log N \log N)\) となります。
• 空間計算量: グラフの隣接リストや距離配列を保持するため、\(O(N + M)\) となります。

実装のポイント

• 時間 \(T\) や辺の重み \(W_j\) が最大 \(10^9\) であり、経路の合計時間が int 型の範囲を超える可能性があるため、long long 型を使用してオーバーフローを防ぐ必要があります。

• ダイクストラ法を開始する前に、始点と終点の危険度が \(K\) 以下であるかを確認することが重要です。これを忘れると、危険度の高い始点や終点からスタートしてしまうバグが発生します。

• C++でダイクストラ法を実装する際、優先度付きキュー（priority_queue）には {距離, 頂点} のペアを使い、距離が小さい順に取り出せるように greater<> を指定します。

  ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const long long INF = 1e18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    long long T;
    if (!(cin >> N >> M >> T)) return 0;
    
    vector<long long> P(N);
    for (int i = 0; i < N; ++i) {
        cin >> P[i];
    }
    
    vector<vector<pair<int, long long>>> adj(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        --u; --v;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    vector<long long> vals = P;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    
    int l = 0, r = vals.size() - 1;
    
    while (l < r) {
        int mid = (l + r) / 2;
        long long K = vals[mid];
        
        if (P[0] > K || P[N - 1] > K) {
            l = mid + 1;
            continue;
        }
        
        vector<long long> dist(N, INF);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
        
        dist[0] = 0;
        pq.push({0, 0});
        bool ok = false;
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            if (d > dist[u]) continue;
            
            if (u == N - 1) {
                if (d <= T) ok = true;
                break;
            }
            
            for (auto& edge : adj[u]) {
                int v = edge.first;
                long long w = edge.second;
                
                if (P[v] > K) continue;
                
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.push({dist[v], v});
                }
            }
        }
        
        if (ok) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    
    cout << vals[l] << "\n";
    
    return 0;
}

この解説は or-glm5.2-high によって生成されました。