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 along the path is minimized.

Analysis

This problem has a typical structure of finding a “minimized maximum value”. For such problems, using binary search is highly effective.

Specifically, by considering the decision problem “Is it possible to make the maximum risk of the path at most \(K\)?”, we can narrow down the value of \(K\) using binary search. Once \(K\) is fixed, the decision problem reduces to “Can we reach vertex \(N\) from vertex \(1\) in at most \(T\) time without passing through vertices with a risk greater than \(K\)?”. This can be determined by finding the shortest path on the graph after removing the unreachable vertices.

Naively finding the shortest path for all possible values of \(K\) would be too slow and result in TLE (Time Limit Exceeded). However, by using binary search, we can significantly reduce the number of checks and solve the problem within the time limit.

Algorithm

1. Prepare candidate answers: Collect the risk values \(P_i\) of all vertices, remove duplicates, and sort them to create an array vals. We will perform a binary search on this array.
2. Binary Search: Choose the middle index mid of the search range, and set the maximum allowed risk to \(K = \text{vals[mid]}\).
3. Decision (Dijkstra’s Algorithm):
   • If the risk of either the starting vertex (vertex \(1\)) or the ending vertex (vertex \(N\)) exceeds \(K\), it is impossible to reach the destination with this \(K\). Thus, we raise the lower bound of the search range to mid + 1.
   • Otherwise, we find the shortest time from vertex \(1\) to vertex \(N\) using Dijkstra’s algorithm. However, we must avoid traversing any vertex whose risk exceeds \(K\).
   • If the computed shortest time is at most \(T\), then this \(K\) satisfies the condition, and a smaller valid \(K\) might exist. Therefore, we lower the upper bound of the search range to mid.
   • If the shortest time exceeds \(T\), the condition is not satisfied. Thus, we raise the lower bound of the search range to mid + 1.
4. Output: The value vals[l] at the end of the binary search will be the answer.

Complexity

• Time Complexity: Assuming the number of unique risk values is \(O(N)\), the binary search takes \(O(\log N)\) iterations. In each iteration, we run Dijkstra’s algorithm, which takes \(O(M \log N)\) time. Therefore, the overall time complexity is \(O(M \log N \log N)\).
• Space Complexity: \(O(N + M)\) to store the graph’s adjacency list and the distance array.

Implementation Points

• Since the time \(T\) and edge weights \(W_j\) can be up to \(10^9\), the total travel time of the path might exceed the range of a standard 32-bit integer (int). Therefore, you should use a 64-bit integer type (such as long long in C++) to prevent overflow.

• It is crucial to check whether the risks of the starting and ending vertices are at most \(K\) before starting Dijkstra’s algorithm. Forgetting this check can lead to bugs where the search starts from or ends at a vertex with a risk higher than \(K\).

• When implementing Dijkstra’s algorithm in C++, use pairs of {distance, vertex} in a priority queue (priority_queue), and specify greater<> so that elements are retrieved in ascending order of distance.

  Source Code

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

---

This editorial was generated by or-glm5.2-high.