概要

本問題は、危険度の最大値を最小化しつつ、所要時間を \(T\) 以下にする経路を求める問題です。「最大値の最小化」という特徴から、「危険度の最大値を \(X\) 以下に抑えたとき、所要時間 \(T\) 以内でゴールできるか？」 という判定問題に言い換え、二分探索（答えの決め打ち二分探索） と ダイクストラ法 を組み合わせて解くことができます。

考察

1. 判定問題への言い換え（単調性の利用）

直接「危険度の最大値の最小値」を求めるのは難しいですが、目標とする危険度の上限 \(X\) を固定してみましょう。

• 危険度の上限を \(X\) と定めたとき、危険度が \(X\) を超える地点（\(P_i > X\)）は一切通ることができません。
• この制限のもとで、地点 \(1\) から地点 \(N\) への最短所要時間を求め、それが \(T\) 以下であるかを判定します。

ここで、上限 \(X\) を大きくすればするほど、通ることができる地点の選択肢が増えるため、最短所要時間は短くなる（または変わらない）という単調性が成り立ちます。 したがって、この判定問題の結果は \(X\) に対して「 \(\text{False}, \text{False}, \dots, \text{True}, \text{True}\) 」のように境界を境に変化します。この境界となる最小の \(X\) を二分探索によって効率的に見つけることができます。

2. 探索範囲の絞り込み

危険度 \(X\) の候補は、存在する地点の危険度 \(P_i\) のいずれかになります。そのため、あらかじめすべての \(P_i\) を集めてソートし、重複を排除した配列（候補リスト）を作成しておきます。

また、スタート地点 \(1\) とゴール地点 \(N\) は必ず通る必要があるため、達成可能な危険度の最小値は少なくとも \(\max(P_1, P_N)\) 以上になります。二分探索の探索範囲の下限をこの値に設定することで、探索の無駄を省くことができます。

アルゴリズム

ステップ 1: 危険度候補の整理

1. すべての地点の危険度 \(P_1, \dots, P_N\) を配列 candidates に格納します。
2. candidates を昇順にソートし、重複する値を取り除きます。
3. 開始地点と終了地点の危険度から、あり得る最小の危険度 min_possible = max(P[1], P[N]) を計算し、candidates の中での位置（インデックス）を二分探索（std::lower_bound）で特定します。これを二分探索の初期探索範囲の下限とします。

ステップ 2: 二分探索

candidates のインデックスに対して二分探索を行います。 * ok: 条件（所要時間 \(T\) 以下で到達可能）を満たすことがわかっているインデックス（初期値は candidates の末尾）。 * ng: 条件を満たさないことがわかっているインデックス（初期値は min_possible の位置の1つ手前）。

ok と ng の差が 1 になるまで、中央値 mid について判定を行います。

ステップ 3: 判定関数 check(X)（ダイクストラ法）

危険度の上限を \(X\) としたとき、以下の手順で判定を行います。 1. \(P_1 > X\) または \(P_N > X\) の場合は、スタート・ゴールすら通れないため即座に false を返します。 2. 危険度が \(X\) 以下の頂点のみを通行可能として、地点 \(1\) からの最短経路をダイクストラ法で求めます。 - 遷移の際、移動先の頂点 \(v\) の危険度 \(P_v\) が \(X\) を超えている場合は、キューへの追加をスキップします。 3. 地点 \(N\) への最短距離が \(T\) 以下であれば true、そうでなければ false を返します。

計算量

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

  • 危険度の候補のソートと重複排除に \(O(N \log N)\) かかります。
  • 二分探索のステップ数は最大で \(O(\log N)\) 回です。
  • 各ステップで実行するダイクストラ法の時間計算量は \(O(M \log N)\) です。
  • したがって、全体の計算量は \(O(N \log N + M \log N \log N)\) となり、制約の \(N \le 2 \times 10^4, M \le 4 \times 10^4\) に対して十分高速に動作します。

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

  • グラフの隣接リストの保持に \(O(N + M)\)、ダイクストラ法の距離配列や優先度付きキューに \(O(N)\) のメモリを使用します。

実装のポイント

• オーバーフローの防止: 所要時間の合計や上限 \(T\) は最大で \(10^9\)、また辺の重みの合計はそれを超える可能性があるため、最短距離を管理する配列や優先度付きキューの要素、無限大を表す定数 INF は long long 型（64ビット整数）を使用する必要があります。

• 無駄な探索の回避: ダイクストラ法の途中で、キューから取り出した現時点での最短距離 d がすでに地点 \(N\) への暫定の最短距離（あるいは \(T\)）を超えている場合は、それ以上の探索を打ち切る（枝刈り）ことで定数倍の高速化が図れます。

  ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

struct Edge {
    int to;
    long long weight;
};

int N, M;
long long T;
vector<long long> P;
vector<vector<Edge>> adj;

bool check(long long X) {
    if (P[1] > X || P[N] > X) return false;
    
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    vector<long long> dist(N + 1, INF);
    
    dist[1] = 0;
    pq.push({0, 1});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (u == N) {
            return d <= T;
        }
        
        if (d > dist[u]) continue;
        
        for (const auto& edge : adj[u]) {
            int v = edge.to;
            long long w = edge.weight;
            if (P[v] > X) continue;
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist[N] <= T;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    if (!(cin >> N >> M >> T)) return 0;
    
    P.resize(N + 1);
    vector<long long> candidates;
    for (int i = 1; i <= N; ++i) {
        cin >> P[i];
        candidates.push_back(P[i]);
    }
    
    adj.resize(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    sort(candidates.begin(), candidates.end());
    candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());
    
    // 危険度の最小値は少なくとも max(P[1], P[N]) 以上
    long long min_possible = max(P[1], P[N]);
    auto it = lower_bound(candidates.begin(), candidates.end(), min_possible);
    int start_idx = distance(candidates.begin(), it);
    
    int ng = start_idx - 1;
    int ok = candidates.size() - 1;
    
    while (ok - ng > 1) {
        int mid = ng + (ok - ng) / 2;
        if (check(candidates[mid])) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    
    cout << candidates[ok] << "\n";
    
    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。