Overview

This problem asks us to find a path from the start (vertex \(1\)) to the goal (vertex \(N\)) in a given weighted undirected graph such that the travel time is at most \(T\), while minimizing the maximum “danger value” of the vertices visited along the path.

Analysis

Difficulty of a Naive Approach

If we try to achieve two objectives simultaneously—finding the shortest path and minimizing the danger value—the state representation becomes complex. For example, if we consider a dynamic programming (DP) approach where we maintain “the shortest time to reach each vertex with a danger value of at most \(x\),” the danger values can be as large as \(10^9\). This would exceed the memory and time limits.

Key Observation: Monotonicity and Binary Search

Here, let’s reverse our perspective and consider the following decision problem: “Is it possible to reach the goal within time \(T\) if we restrict the danger value of the visited vertices to be at most \(X\)?”

This decision problem satisfies the following monotonicity: - As the allowed danger value \(X\) increases, more vertices become accessible, making it easier to reach the goal within time \(T\). - Conversely, if the danger value \(X\) is too small, the accessible vertices are restricted, making it impossible to reach the goal.

When there exists a boundary where the condition is satisfied for any value greater than or equal to \(X\), and not satisfied for any value less than \(X\), we can efficiently find the optimal \(X\) using binary search.

Solving the Decision Problem (Dijkstra’s Algorithm)

When the danger value \(X\) is fixed, we cannot visit any vertex with a danger value strictly greater than \(X\). Therefore, we only need to find the shortest path from vertex \(1\) to vertex \(N\) in the subgraph consisting only of vertices with a danger value of at most \(X\), and check if the travel time is at most \(T\). This can be solved in \(O(M \log N)\) time using Dijkstra’s algorithm.

---

Algorithm

1. Identifying Candidates for the Danger Value

   • The danger values we might encounter along the path are among the given vertex danger values \(P_i\).
   • However, since we must pass through the start vertex \(1\) and the goal vertex \(N\), the minimum possible danger value of the path is at least \(\max(P_1, P_N)\).
   • Therefore, we extract unique values from \(P\) that are greater than or equal to \(\max(P_1, P_N)\), and sort them in ascending order to create an array \(A\). The elements of \(A\) will be the search space (candidates for the danger value \(X\)) for our binary search.

2. Executing the Binary Search

   • Set the left bound of the search range to low = 0 and the right bound to high = len(A) - 1.
   • Let mid = (low + high) // 2, and call the decision function check(X) with danger value \(X = A[mid]\).
     • If check(X) is True: Since the goal is reachable with danger value \(X\), we search for a smaller danger value by setting high = mid - 1 and updating our tentative answer.
     • If check(X) is False: Since the goal is unreachable with danger value \(X\), we need to allow a larger danger value, so we set low = mid + 1.

3. Details of the Decision Function check(X)

   • Initialize an array dist storing the shortest distance from the start vertex \(1\) with a sufficiently large value (such as \(T + 1\)).
   • Run Dijkstra’s algorithm using a priority queue (heap).
   • We only update the shortest distance and push to the queue if the destination vertex \(v\) satisfies \(P_v \leq X\).
   • Terminate the search and return True as soon as the goal vertex \(N\) is reached. If the queue becomes empty and the goal has not been reached, return False.

---

Complexity

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

  • Let \(U\) be the number of unique danger values (\(U \leq N\)). The number of steps in the binary search is \(O(\log U)\).
  • In each step, the time complexity of running Dijkstra’s algorithm is \(O(M \log N)\).
  • The overall time complexity is \(O(M \log N \log U) \subseteq O(M \log^2 N)\), which is well within the time limit under the given constraints (\(N \le 2 \times 10^4, M \le 4 \times 10^4\)).

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

  • The adjacency list adj representing the graph uses \(O(N + M)\) memory, and the shortest distance array dist and the priority queue use \(O(N)\) memory.

---

Implementation Tips

• Reducing the Search Range: By excluding danger values strictly less than \(\max(P_1, P_N)\) from the binary search candidates beforehand, we can reduce the number of binary search steps and avoid redundant searches in Dijkstra’s algorithm.

• Fast I/O: In Python, when the number of input lines is large, reading all inputs at once using sys.stdin.read().split() can eliminate I/O bottlenecks.

  Source Code

import heapq
import sys


def solve():
    # 入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])
    T = int(input_data[2])

    P = [int(x) for x in input_data[3 : 3 + N]]

    adj = [[] for _ in range(N)]
    idx = 3 + N
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx + 1]) - 1
        w = int(input_data[idx + 2])
        adj[u].append((v, w))
        adj[v].append((u, w))
        idx += 3

    # 起点と終点の危険度の最大値が、探索する危険度の下限となる
    P_start_end = max(P[0], P[N - 1])
    P_unique = sorted(list(set(P)))
    A = [x for x in P_unique if x >= P_start_end]

    # 危険度 X 以下の頂点のみを用いて、時間 T 以内にゴールできるか判定
    def check(X):
        dist = [T + 1] * N
        dist[0] = 0
        pq = [(0, 0)]  # (d, u)
        while pq:
            d, u = heapq.heappop(pq)
            if u == N - 1:
                return True
            if d > dist[u]:
                continue
            for v, w in adj[u]:
                if P[v] <= X:
                    nd = d + w
                    if nd < dist[v]:
                        dist[v] = nd
                        heapq.heappush(pq, (nd, v))
        return False

    # 二分探索
    low = 0
    high = len(A) - 1
    ans = A[high]

    while low <= high:
        mid = (low + high) // 2
        if check(A[mid]):
            ans = A[mid]
            high = mid - 1
        else:
            low = mid + 1

    print(ans)


if __name__ == "__main__":
    solve()

---

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