概要

通過地点数 \(K\) 以下で地点 \(1\) から地点 \(N\) に到達できるルートのうち、ルート上の標高の最大値（最高標高）を最小化します。
「ある最高標高以下で到達可能か？」を判定し、それを二分探索で最小化します。

考察

重要な気づき

• 最高標高を \(x\) 以下に抑えるとは、「標高 \(H_i \le x\) の地点だけを使って」地点 \(1\) から地点 \(N\) へ行ける、ということです。
• 通過地点数が \(K\) 以下という制約は、辺の本数（移動回数）でいうと \(K-1\) 以下です（地点数 = 辺数 + 1）。
• さらに問題では「同じ地点を2度通らない（単純路）」という条件がありますが、最短路（最小辺数の路）は必ず単純路です。
  したがって「辺数 \(K-1\) 以下で到達可能か？」を BFSで最短距離を調べれば十分です（単純路条件を個別に扱う必要がありません）。

素朴な方法が難しい理由

• 最高標高の候補は最大で \(10^9\) まであり、そのまま全探索するのは不可能です。
• さらに、ルート（単純路）を直接列挙するのも組合せ爆発します。

解決方針

• 最高標高の候補は実は「どれかの地点の標高」に限ってよいです（最適値は必ずある \(H_i\) に一致）。
• よって、標高を小さい順に並べた配列に対し二分探索し、
  • 「標高 \(\le x\) の地点だけで作った部分グラフで、\(1 \to N\) の最短距離が \(K-1\) 以下か？」 を BFS で判定します。

アルゴリズム

1. 標高配列 \(H\) から重複を除いたものを昇順に並べ、heights_sorted を作る。
2. 判定関数 feasible(x) を用意する：
   • もし \(H_1 > x\) または \(H_N > x\) なら即 False（出発・到着が使えない）。
   • BFS を行う。ただし標高 \(> x\) の地点は訪問禁止。
   • 距離（辺数）dist を管理し、dist[N] \le K-1 なら True。
   • BFS 中に距離がすでに \(K-1\) に達した頂点からはこれ以上伸ばさない（枝刈り）。
3. まず最大候補（heights_sorted[-1]）でも到達不可能なら答えは -1。
4. そうでなければ heights_sorted 上で二分探索し、feasible が True になる最小の \(x\) を探して出力。

計算量

• 時間計算量: \(O((N+M)\log N)\)
  （BFSが \(O(N+M)\)、二分探索が高々 \(\log(\text{ユニーク標高数}) \le \log N\) 回）
• 空間計算量: \(O(N+M)\)
  （隣接リストと BFS 用の距離配列）

実装のポイント

• 通過地点数 \(K\) は辺数制限に直すと max_edges = K-1 になる点に注意します。

• 「単純路」の条件は、BFS が返す最短路が必ず単純路であるため、追加の処理は不要です。

• feasible 内では以下の枝刈りが効きます：

  • du == max_edges の頂点から先へ進まない（これ以上伸ばしても制限超過）。
  • 到達点 \(N\) を見つけた時点で即 return（早期終了）。

• 入力は \(10^5, 2\times 10^5\) 規模なので、sys.stdin.buffer.readline と隣接リストで高速化します。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。