Overview

This problem asks whether it is possible to reach location \(N\) from location \(1\) in at most time \(T\), while minimizing the maximum risk of the visited locations.

Once we fix the “upper bound of risk”, we only need to find the shortest path using locations with risk less than or equal to this bound. Thus, we can solve this problem by combining binary search and Dijkstra’s algorithm.

Analysis

The risk of a path is the maximum risk among all visited locations.

For example, let’s fix a value \(X\) and consider the following:

Can we reach location \(N\) from location \(1\) in at most time \(T\), using only locations with risk at most \(X\)?

This becomes a problem of finding the shortest path using only the remaining locations, after excluding locations with risk strictly greater than \(X\) from the graph.

Important Monotonicity

If it is possible to reach the destination with a risk upper bound \(X\), then it is also possible with any larger upper bound \(Y \ge X\).

This is because a larger bound \(Y\) only increases the set of usable locations and never reduces the available paths.

Thus, the decision results exhibit monotonicity as follows:

Risk upper bound: Small -------------------- Large
Decision result:  false false false true true true

Due to this monotonicity, we can binary search for the answer.

Candidates for the Answer

The risk of a path is the “maximum risk of the visited locations.”

Therefore, the answer must be the risk \(P_i\) of one of the locations.

Thus, although we could binary search directly over the range \([0, 10^9]\), in this implementation we collect all \(P_i\) values, remove duplicates, and perform binary search on the resulting sorted array vals.

Why a Naive Approach is Difficult

Enumerating all paths and finding one with a travel time of at most \(T\) is impossible because the number of paths can be extremely large.

Furthermore, running Dijkstra’s algorithm for every single candidate risk would take about

\(O(N \times (N+M)\log N)\)

which is too slow to pass within the time limit.

Therefore, we use binary search utilizing the monotonicity to reduce the number of Dijkstra’s algorithm runs to \(O(\log N)\).

Algorithm

First, we collect the risk \(P_i\) of each location, sort them in ascending order, and remove duplicates to construct an array vals.

Next, we consider the following decision function ok(lim).

Decision Function ok(lim)

Let lim be the upper bound of the risk.

• Locations with risk strictly greater than lim cannot be used.
• Determine whether we can reach location \(N\) from location \(1\) in at most time \(T\) using only the usable locations.

Specifically, we do the following:

1. If the risk of the starting location \(1\) or the destination location \(N\) exceeds lim, it is impossible, so return false.
2. Find the shortest time from location \(1\) to all other locations using Dijkstra’s algorithm.
3. When traversing an edge, if the risk of the destination location exceeds lim, ignore that transition.
4. If the shortest time to location \(N\) is at most \(T\), return true.

Since the time \(W_j\) for all trails is positive, the shortest path can be found using Dijkstra’s algorithm.

Binary Search

We perform a binary search on vals to find the first index \(i\) where ok(vals[i]) becomes true.

The smaller vals[i] is, the stricter the condition.
The larger vals[i] is, the looser the condition.

Thus, the minimum vals[i] that satisfies the condition is the answer.

Complexity

Let \(K\) be the number of unique risk values. Note that \(K \le N\).

• Per Dijkstra’s algorithm run: \(O((N+M)\log N)\)
• Number of binary search steps: \(O(\log K)\)

Therefore,

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

Implementation Points

• Since distances, times, and risks can be up to \(10^9\), the total time may exceed the range of a standard 32-bit integer. Use long long.

• Inside ok(lim), do not transition to locations whose risk exceeds lim.

• During Dijkstra’s algorithm, if the distance already exceeds \(T\), we can prune the search since continuing further will only increase the time.

• The location indices are 1-based in the input, but they are converted to 0-based in the implementation.

• Even if there are multiple trails connecting the same two locations, you can add them directly to the adjacency list without any issues.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long T;
    cin >> N >> M >> T;

    vector<long long> P(N);
    for (int i = 0; i < N; i++) cin >> P[i];

    vector<vector<pair<int, long long>>> g(N);
    for (int i = 0; i < M; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        --u; --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    vector<long long> vals = P;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    auto ok = [&](long long lim) -> bool {
        if (P[0] > lim || P[N - 1] > lim) return false;

        const long long INF = (1LL << 62);
        vector<long long> dist(N, INF);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

        dist[0] = 0;
        pq.push({0, 0});

        while (!pq.empty()) {
            auto [d, v] = pq.top();
            pq.pop();

            if (d != dist[v]) continue;
            if (d > T) continue;
            if (v == N - 1) return d <= T;

            for (auto [to, w] : g[v]) {
                if (P[to] > lim) continue;
                long long nd = d + w;
                if (nd < dist[to] && nd <= T) {
                    dist[to] = nd;
                    pq.push({nd, to});
                }
            }
        }

        return false;
    };

    int ng = -1, ok_idx = (int)vals.size() - 1;
    while (ok_idx - ng > 1) {
        int mid = (ng + ok_idx) / 2;
        if (ok(vals[mid])) ok_idx = mid;
        else ng = mid;
    }

    cout << vals[ok_idx] << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.