Overview

This problem asks us to find a path that keeps the total travel time at most \(T\) while minimizing the maximum risk level of the visited locations. Due to the characteristic of “minimizing the maximum value,” we can rephrase this into a decision problem: “Can we reach the goal within time \(T\) if we limit the maximum risk level to at most \(X\)?” This allows us to solve the problem by combining binary search (binary search on the answer) and Dijkstra’s algorithm.

Analysis

1. Reformulating as a Decision Problem (Using Monotonicity)

Directly finding the “minimum of the maximum risk level” is difficult, so let us fix the target upper limit of the risk level, \(X\).

• When we set the upper limit of the risk level to \(X\), we cannot pass through any location whose risk level exceeds \(X\) (\(P_i > X\)).
• Under this restriction, we find the shortest travel time from location \(1\) to location \(N\) and determine whether it is at most \(T\).

Here, as the upper limit \(X\) increases, the set of reachable locations expands (or remains the same), meaning the shortest travel time will decrease (or remain unchanged). This property is called monotonicity. Therefore, the result of this decision problem as a function of \(X\) changes from “\(\text{False}, \text{False}, \dots, \text{True}, \text{True}\)” at a certain boundary. We can efficiently find the minimum \(X\) at this boundary using binary search.

2. Narrowing Down the Search Range

The candidates for the risk level \(X\) are the risk levels of the existing locations, \(P_i\). Therefore, we can collect all \(P_i\), sort them, and remove duplicates to create an array of candidates (a candidate list).

Furthermore, since we must pass through the start location \(1\) and the goal location \(N\), the minimum achievable risk level must be at least \(\max(P_1, P_N)\). By setting the lower bound of the binary search range to this value, we can avoid redundant searches.

Algorithm

Step 1: Organizing the Risk Level Candidates

1. Store the risk levels of all locations \(P_1, \dots, P_N\) in an array candidates.
2. Sort candidates in ascending order and remove duplicate values.
3. Based on the risk levels of the start and goal locations, calculate the minimum possible risk level min_possible = max(P[1], P[N]), and locate its index in candidates using binary search (std::lower_bound). Use this index as the lower bound of the initial binary search range.

Step 2: Binary Search

Perform binary search on the indices of candidates. * ok: An index known to satisfy the condition (reachable within time \(T\)). The initial value is the last index of candidates. * ng: An index known to not satisfy the condition. The initial value is one position before the index of min_possible.

While the difference between ok and ng is greater than 1, evaluate the condition for the middle index mid.

Step 3: Decision Function check(X) (Dijkstra’s Algorithm)

With the upper limit of the risk level set to \(X\), perform the evaluation using the following steps: 1. If \(P_1 > X\) or \(P_N > X\), we cannot even visit the start or goal locations, so immediately return false. 2. Assuming only vertices with a risk level of at most \(X\) are traversable, find the shortest path from location \(1\) using Dijkstra’s algorithm. - During transitions, if the risk level \(P_v\) of the destination vertex \(v\) exceeds \(X\), skip adding it to the queue. 3. If the shortest distance to location \(N\) is at most \(T\), return true; otherwise, return false.

Complexity

• Time Complexity: \(O(N \log N + M \log N \log N)\)

  • Sorting and removing duplicates from the risk level candidates takes \(O(N \log N)\) time.
  • The number of binary search steps is at most \(O(\log N)\).
  • The time complexity of Dijkstra’s algorithm executed in each step is \(O(M \log N)\).
  • Thus, the overall time complexity is \(O(N \log N + M \log N \log N)\), which is fast enough for the constraints \(N \le 2 \times 10^4, M \le 4 \times 10^4\).

• Space Complexity: \(O(N + M)\)

  • It uses \(O(N + M)\) memory to store the adjacency list of the graph, and \(O(N)\) memory for Dijkstra’s distance array and priority queue.

Implementation Details

• Preventing Overflow: The total travel time and the limit \(T\) can be up to \(10^9\), and the sum of edge weights can exceed this value. Therefore, the array for managing shortest distances, the elements in the priority queue, and the constant representing infinity (INF) must use the long long type (64-bit integer).

• Avoiding Redundant Search: During Dijkstra’s algorithm, if the current shortest distance d popped from the queue already exceeds the temporary shortest distance to location \(N\) (or \(T\)), we can prune the search (terminate early). This optimizes the execution time by a constant factor.

  Source Code

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

---

This editorial was generated by gemini-3.5-flash-high.