Overview

This problem asks whether we can travel from vertex \(1\) to vertex \(N\) in a total time of \(T\) or less, while minimizing the maximum danger level of the visited vertices.

If we fix the “upper bound of the danger level”, we only need to solve the shortest path problem using only the vertices whose danger levels are less than or equal to this bound. Thus, we can perform a binary search on the danger level.

Analysis

The danger level of a path is the maximum danger level among all the vertices visited along the path.

For example, suppose we choose a value \(X\) and can determine the following:

Is it possible to travel from vertex \(1\) to vertex \(N\) in a total time of \(T\) or less, using only vertices with a danger level of \(X\) or less?

This decision problem has monotonicity:

• If it is possible with an upper bound \(X\), it is also possible with any larger bound \(Y \geq X\).
• If it is impossible with an upper bound \(X\), it is also impossible with any smaller bound.

This is because increasing the upper bound only increases (or keeps the same) the set of usable vertices, and never decreases it.

Therefore, we can find the minimum possible danger level (the answer) using binary search.

Feasibility Check

Let the upper bound of the danger level be limit.

In this case, the only allowed vertices are those satisfying \(P_i \leq \text{limit}\).

Using only these vertices, we find the shortest path (minimum time) from vertex \(1\) to vertex \(N\).

Since the travel time \(W_j\) of each trail is positive, we can find the shortest path using Dijkstra’s algorithm.

If the shortest time is \(T\) or less, then it is reachable under this limit.

Why a Naive Approach is Infeasible

Enumerating all paths is impossible because we can visit the same vertices and trails multiple times.

Furthermore, if we try all candidate danger levels in ascending order and run Dijkstra’s algorithm each time, we would have to execute Dijkstra’s algorithm up to \(N\) times, which is too slow under the time limit.

Therefore, by using binary search based on monotonicity, we can reduce the number of times we run Dijkstra’s algorithm to \(O(\log N)\).

Algorithm

First, the candidates for the danger level are the danger levels \(P_i\) of the vertices.

Since the danger level of a path is the “maximum danger level of the visited vertices”, the answer must be equal to the danger level of some vertex.

Thus, we can obtain the sorted, unique danger level candidates in ascending order using sorted(set(P)).

Note that since the path must start at vertex \(1\) and end at vertex \(N\), the answer must be at least:

\[ \max(P_1, P_N) \]

We can start our binary search from this minimum possible value.

In the decision function feasible(limit), we do the following:

1. If \(P_1 > \text{limit}\) or \(P_N > \text{limit}\), it is unreachable (return False).
2. Calculate the shortest time from vertex \(1\) using Dijkstra’s algorithm.
3. Do not move to any vertex whose danger level exceeds limit.
4. If vertex \(N\) can be reached in a total time of \(T\) or less, return True.
5. Otherwise, return False.

During Dijkstra’s algorithm, paths with a total time exceeding \(T\) are not useful, so we only push to the heap when nd <= T.

Using binary search, we find the minimum limit for which feasible(limit) returns True.

Complexity

Let \(K\) be the number of unique danger levels. Note that \(K \leq N\).

A single feasibility check runs Dijkstra’s algorithm, which takes:

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

Since we perform this check \(O(\log K)\) times during the binary search, the overall complexity is as follows:

• Time Complexity: \(O((N+M)\log N \log K)\)
  Since \(K \leq N\), this can also be written as \(O((N+M)\log^2 N)\).
• Space Complexity: \(O(N+M)\)

Implementation Points

• Since the graph is undirected, add each edge in both directions.

• In Dijkstra’s algorithm, only transition to vertices whose danger levels are less than or equal to limit.

• Set INF = T + 1. Since we only care about whether we can reach the destination in \(T\) or less, any distance exceeding \(T\) is unnecessary.

• If the distance popped from the heap is different from the current dist[v], ignore it as it is outdated.

• The moment vertex \(N\) is popped from the heap, its shortest distance is finalized, so we can immediately return True.

• Since the edge weights and \(T\) can be as large as \(10^9\), you need to use 64-bit integers (such as long long in C++) when implementing in other languages.

  Source Code

import sys
import heapq
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    N = int(next(it))
    M = int(next(it))
    T = int(next(it))

    P = [int(next(it)) for _ in range(N)]
    adj = [[] for _ in range(N)]

    for _ in range(M):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        w = int(next(it))
        adj[u].append((v, w))
        adj[v].append((u, w))

    target = N - 1
    INF = T + 1

    def feasible(limit):
        if P[0] > limit or P[target] > limit:
            return False

        dist = [INF] * N
        dist[0] = 0
        hq = [(0, 0)]
        heappush = heapq.heappush
        heappop = heapq.heappop

        while hq:
            d, v = heappop(hq)
            if d != dist[v]:
                continue
            if v == target:
                return True

            for to, w in adj[v]:
                if P[to] <= limit:
                    nd = d + w
                    if nd <= T and nd < dist[to]:
                        dist[to] = nd
                        heappush(hq, (nd, to))

        return False

    vals = sorted(set(P))
    lo = bisect_left(vals, max(P[0], P[target]))
    hi = len(vals) - 1

    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(vals[mid]):
            hi = mid
        else:
            lo = mid + 1

    print(vals[lo])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.