Overview

This problem asks us to find a path from vertex \(1\) to vertex \(N\) with a total travel time of at most \(T\) such that the maximum risk of the vertices visited along the path is minimized. We can solve this using “binary search on the answer + shortest path (Dijkstra’s algorithm)”.

Analysis

Key Insight

What we want to find in this problem is the “minimization of the maximum risk along the path”. This type of “minimax” (minimizing the maximum) problem is highly compatible with binary search.

Let us consider the following decision problem:

When the upper bound of the risk is fixed to \(D\), is it possible to reach vertex \(N\) from vertex \(1\) in a travel time of at most \(T\), passing only through vertices with a risk of at most \(D\)?

This decision problem exhibits monotonicity. That is, if it is possible to reach the destination with a certain \(D\), it is always possible with any larger \(D'\) (\(D' > D\)). This is because increasing the limit only expands the set of allowed vertices and never reduces the available paths.

Conversely, if it is impossible with a certain \(D\), it is also impossible with any smaller \(D\).

Due to this monotonicity, we can use binary search to find the minimum \(D\) for which the destination is reachable.

Decision Problem for a Fixed Risk \(D\)

Fixing the risk to \(D\) imposes the constraint “vertices with a risk strictly greater than \(D\) cannot be passed”. Thus, we can:

• Disable (forbid) all vertices with a risk strictly greater than \(D\).
• Find the shortest travel time from vertex \(1\) to vertex \(N\) using only the remaining vertices.

If this shortest time is at most \(T\), we can determine that it is “feasible”. This can be computed using the standard Dijkstra’s algorithm.

Note that the starting vertex \(1\) and the destination vertex \(N\) are also subject to the risk constraint. If \(P_1 > D\) or \(P_N > D\), we cannot even start or finish the journey, so it is immediately infeasible.

Issues with a Naive Approach

Since the risk values can span a wide range (\(0 \le P_i \le 10^9\)), performing a linear search starting from \(0\), or performing a binary search directly on the integer range \([0, 10^9]\) for \(D\), would be inefficient.

In fact, the possible values of \(D\) that can be the optimal answer are restricted to the risk values \(P_i\) of the vertices themselves (since we are taking the maximum, the optimal value must coincide with the risk of some vertex). Therefore, we can collect all \(P_i\) values, sort and remove duplicates to form a list of candidate values, and then binary search over the indices of this candidate array for efficiency.

Algorithm

1. Collect the risk values \(P_i\) of all vertices, sort them, and remove duplicates to create a candidate array cand.
2. Perform a binary search on the indices of the candidate array.
3. For each \(D = \) cand[mid], solve the decision problem:
   • If \(P_1 > D\) or \(P_N > D\), it is impossible.
   • Run Dijkstra’s algorithm to find the shortest travel time from vertex \(1\) to vertex \(N\) on the graph, excluding any vertices with a risk strictly greater than \(D\).
   • If the shortest time is at most \(T\), it is feasible.
4. The minimum cand[mid] that is feasible is the answer.

In the binary search, we use the standard “find the minimum value that satisfies the condition” pattern: “if feasible(mid) is true, update the answer to mid and search the left side (hi = mid - 1); if false, search the right side (lo = mid + 1)”.

Complexity

Since the number of candidates is at most \(N\), the binary search takes \(O(\log N)\) steps. Each step runs Dijkstra’s algorithm, which takes \(O((N + M) \log N)\) time.

• Time Complexity: \(O((N + M) \log N \cdot \log N) = O((N+M) \log^2 N)\)
• Space Complexity: \(O(N + M)\)

Since \(N \le 2 \times 10^4\) and \(M \le 4 \times 10^4\), this approach runs well within the time limit.

Implementation Details

• Preventing Overflow: Since \(W_j \le 10^9\) and the same edge might be traversed multiple times along a path, the total distance can become very large. Use long long to represent distances, and define INF as a sufficiently large value that does not overflow when added to other values (e.g., LLONG_MAX / 4).

• Excluding Vertices in Dijkstra: When relaxing an adjacent vertex \(v\), we can naturally forbid visiting vertices with a risk greater than \(D\) by adding a check like if (P[v] > D) continue;. Note that the start and destination vertices should be checked separately at the beginning of the function.

• Early Termination: In Dijkstra’s algorithm, the distance to a vertex is finalized the first time it is popped from the priority queue. Thus, we can speed up the algorithm slightly by terminating early as soon as we pop u == N (since dist[N] is already determined at this point).

• Creating Candidates: Applying sort followed by unique + erase to remove duplicates ensures that the binary search works correctly and avoids redundant search steps.

  Source Code

#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;
}

---

This editorial was generated by claude4.8opus-high.