Overview

Among all routes from point \(1\) to point \(N\) that pass through at most \(K\) points, we want to minimize the maximum elevation along the route (the highest elevation). We determine “Is it possible to reach the destination with the highest elevation at most some value?” and minimize this value using binary search.

Analysis

Key Observations

• Keeping the highest elevation at most \(x\) means “using only points with elevation \(H_i \le x\)” to travel from point \(1\) to point \(N\).
• The constraint that the number of points visited is at most \(K\) translates to at most \(K-1\) edges (number of moves), since number of points = number of edges + 1.
• Additionally, the problem requires “not visiting the same point twice (simple path),” but a shortest path (minimum number of edges) is always a simple path. Therefore, it suffices to check the shortest distance using BFS to determine “is it reachable with at most \(K-1\) edges?” (there is no need to handle the simple path condition separately).

Why a Naive Approach Is Difficult

• The candidates for the highest elevation can be up to \(10^9\), making brute-force enumeration infeasible.
• Furthermore, directly enumerating all routes (simple paths) leads to combinatorial explosion.

Solution Strategy

• The candidates for the highest elevation can actually be restricted to “the elevation of some point” (the optimal value always coincides with some \(H_i\)).
• Therefore, we binary search over the array of elevations sorted in ascending order, and for each candidate check:
  • “In the subgraph consisting only of points with elevation \(\le x\), is the shortest distance from \(1 \to N\) at most \(K-1\)?” using BFS.

Algorithm

1. Remove duplicates from the elevation array \(H\), sort in ascending order, and create heights_sorted.
2. Prepare a feasibility function feasible(x):
   • If \(H_1 > x\) or \(H_N > x\), immediately return False (the start or destination cannot be used).
   • Perform BFS, but forbid visiting points with elevation \(> x\).
   • Maintain distance (number of edges) dist, and return True if dist[N] \le K-1.
   • During BFS, do not extend further from vertices whose distance has already reached \(K-1\) (pruning).
3. First, if the destination is unreachable even with the maximum candidate (heights_sorted[-1]), the answer is -1.
4. Otherwise, binary search over heights_sorted to find the minimum \(x\) for which feasible returns True, and output it.

Complexity

• Time complexity: \(O((N+M)\log N)\) (BFS is \(O(N+M)\), and binary search runs at most \(\log(\text{number of unique elevations}) \le \log N\) times)
• Space complexity: \(O(N+M)\) (adjacency list and distance array for BFS)

Implementation Notes

• Note that the number of visited points \(K\) translates to an edge limit of max_edges = K-1.

• The “simple path” condition requires no additional handling, since the shortest path returned by BFS is always a simple path.

• The following pruning techniques are effective within feasible:

  • Do not proceed further from a vertex where du == max_edges (extending further would exceed the limit).
  • Return immediately upon reaching point \(N\) (early termination).

• Since the input scale is on the order of \(10^5\) and \(2\times 10^5\), use sys.stdin.buffer.readline and adjacency lists for speedup.

  Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.buffer.readline
    N, M, K = map(int, input().split())
    H = list(map(int, input().split()))
    adj = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].append(v)
        adj[v].append(u)

    heights_sorted = sorted(set(H))
    target = N - 1
    max_edges = K - 1

    def feasible(x: int) -> bool:
        if H[0] > x or H[target] > x:
            return False
        dist = [-1] * N
        dq = deque([0])
        dist[0] = 0

        while dq:
            u = dq.popleft()
            du = dist[u]
            if u == target:
                return du <= max_edges
            if du == max_edges:
                continue
            for v in adj[u]:
                if dist[v] != -1:
                    continue
                if H[v] > x:
                    continue
                dist[v] = du + 1
                if v == target:
                    return dist[v] <= max_edges
                dq.append(v)
        return False

    if not feasible(heights_sorted[-1]):
        print(-1)
        return

    lo, hi = 0, len(heights_sorted) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(heights_sorted[mid]):
            hi = mid
        else:
            lo = mid + 1
    print(heights_sorted[lo])

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.