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 danger level of the vertices on the path is minimized.

Analysis

This is a classic optimization problem of “minimizing the maximum danger level”. For such problems, it is effective to use binary search to reduce the problem to a decision problem: “Is there a path where the maximum danger level is at most \(X\)?”

A naive approach would be to enumerate all possible paths and find one that satisfies the condition, but this will TLE (Time Limit Exceeded) because the number of paths can be extremely large.

When using binary search, we set a threshold \(X\) and determine whether “it is possible to reach vertex \(N\) from vertex \(1\) within time \(T\) using only vertices with danger levels of at most \(X\)”. This decision problem can be solved by finding the shortest path on a subgraph consisting only of vertices with danger levels at most \(X\). Since we want to minimize the travel time, we can use Dijkstra’s algorithm.

Algorithm

1. Preparation for Binary Search: The candidate values for the danger level are the danger levels of the vertices, \(P_i\). Therefore, we sort the elements of \(P\) and remove duplicates to create a list vals. We will perform binary search on this list. Note that since the starting and destination vertices must be included in the path, we can slightly reduce the search space by setting the lower bound of the binary search to max(P[0], P[N-1]).

2. Decision Function check(X): We check if it is possible to reach the destination within time \(T\) when the maximum allowed danger level is \(X\).

   • If the danger level of vertex \(N\) itself exceeds \(X\), it is clearly unreachable, so we return False.
   • Otherwise, we find the shortest path from vertex \(1\) using Dijkstra’s algorithm. During the search, a vertex \(v\) can only be transitioned to if its danger level is at most \(X\) (\(P_v \leq X\)).
   • Since we do not need to explore paths that take longer than \(T\), we can initialize the distance array dist with \(T+1\) and only push a node into the priority queue if the new distance nd is at most \(T\).
   • Finally, if the shortest time to reach vertex \(N\) is at most \(T\), we return True; otherwise, we return False.

3. Executing the Binary Search: We find the minimum \(X\) such that check(X) is True using binary search, and output it.

Complexity

• Time Complexity: \(O(M \log N \log N)\)
  • Dijkstra’s algorithm takes \(O(M \log N)\) and the binary search runs \(O(\log N)\) times (since \(N\) is the number of vertices, the number of unique values in \(P\) is at most \(N\)).
• Space Complexity: \(O(N + M)\)
  • To store the adjacency list of the graph and the distance array.

Implementation Tips

• To speed up input reading in Python, use sys.stdin.readline.

• By setting the lower bound of the binary search range to max(P[0], P[N-1]), we can avoid redundant searches.

• By adding the condition nd <= T when pushing to the priority queue in Dijkstra’s algorithm, we prune paths that exceed \(T\), achieving a constant-factor speedup.

  Source Code

import sys
import heapq
import bisect

def solve():
    input = sys.stdin.readline
    N, M, T = map(int, input().split())
    P = list(map(int, input().split()))
    adj = [[] for _ in range(N)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].append((v, w))
        adj[v].append((u, w))
        
    def check(X):
        if P[N-1] > X:
            return False
        dist = [T + 1] * N
        dist[0] = 0
        pq = [(0, 0)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            if u == N - 1:
                return True
            for v, w in adj[u]:
                if P[v] <= X:
                    nd = d + w
                    if nd < dist[v]:
                        dist[v] = nd
                        if nd <= T:
                            heapq.heappush(pq, (nd, v))
        return dist[N-1] <= T

    vals = sorted(list(set(P)))
    min_req = max(P[0], P[N-1])
    low = bisect.bisect_left(vals, min_req)
    high = len(vals) - 1
    ans = -1
    while low <= high:
        mid = (low + high) // 2
        if check(vals[mid]):
            ans = vals[mid]
            high = mid - 1
        else:
            low = mid + 1
    print(ans)

if __name__ == '__main__':
    solve()

---

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