概要

地点 \(1\) から地点 \(N\) へ、通過地点数 \(K\) 以下のルートで到達するとき、ルート上の標高の最大値を最小化する問題です。「最大値の最小化」を二分探索 + BFS で解きます。

考察

重要な気づき：最大値の最小化は二分探索と相性が良い

「ルート上の最高標高を最小にしたい」という最適化問題を直接解くのは難しいです。しかし、次のような判定問題に置き換えると扱いやすくなります：

判定問題: 標高の上限を \(T\) としたとき、標高が \(T\) 以下の地点だけを使って、地点 \(1\) から地点 \(N\) へ通過地点数 \(K\) 以下で到達できるか？

この判定問題に対して \(T\) が大きいほど使える地点が増えるため、「\(T\) が小さいと不可能、\(T\) が十分大きいと可能」という単調性があります。よって、\(T\) の値を二分探索で求められます。

素朴なアプローチの問題点

\(T\) を全通り試して毎回 BFS すると、\(T\) の候補が最大 \(N\) 個、BFS が \(O(N + M)\) なので全体で \(O(N(N + M))\) となり、\(N, M\) が大きいと遅くなる可能性があります。しかし \(T\) の候補を二分探索で \(O(\log N)\) に減らせば十分高速です。

二分探索の候補

\(T\) として意味があるのは、実際に存在する標高の値だけです。標高の値をソートして重複を除いた配列を候補とします。さらに、地点 \(1\) と地点 \(N\) は必ず通るため \(T \geq \max(H_1, H_N)\) が必要です。

アルゴリズム

1. 候補の準備: 全地点の標高をソートし、重複を除く。\(\max(H_1, H_N)\) 以上のもののみを候補とする。
2. 二分探索: 候補配列上で二分探索を行う。各候補 \(T\) に対して判定問題を解く。
3. 判定（BFS）: 標高が \(T\) 以下の地点のみを使い、地点 \(1\) から BFS を行う。BFS は最短経路（通過地点数が最小のパス）を求めるので、地点 \(N\) への最短通過地点数が \(K\) 以下かどうかを判定する。
4. 結果: 二分探索で条件を満たす最小の \(T\) を出力する。候補が存在しない、または最大の候補でも到達不可能なら \(-1\) を出力する。

具体例

例えば \(N=4\), \(K=3\), 標高が \(H = [2, 5, 3, 4]\), 辺が \((1,2), (2,4), (1,3), (3,4)\) の場合：

• \(T = 4\) のとき：\(H \leq 4\) の地点は \(\{1, 3, 4\}\)。パス \(1 \to 3 \to 4\) が存在し通過地点数 \(3 \leq K\)。→ 可能
• \(T = 3\) のとき：\(H \leq 3\) の地点は \(\{1, 3\}\)。地点 \(4\)（標高 \(4\)）が使えないので到達不可能。→ 不可能

よって答えは \(4\) です。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • 二分探索の回数が \(O(\log N)\)、各回で BFS が \(O(N + M)\)
• 空間計算量: \(O(N + M)\)
  • 隣接リストと BFS 用の距離配列

実装のポイント

• BFS の距離管理: dist[v] = 0 を「未訪問」として扱い、dist[1] = 1（地点 \(1\) 自身を含む通過地点数が \(1\)）から始めることで、配列の初期化を簡潔にしている。

• 早期打ち切り: 地点 \(N\) に到達した時点で即座に判定結果を返す。また、現在の通過地点数が \(K\) に達したらそれ以上探索しない（d >= K で continue）。

• 最大候補での事前チェック: 二分探索前に最大の候補で到達可能か確認し、不可能なら即 \(-1\) を返す。これにより無駄な探索を避けられる。

  ソースコード

import sys
from collections import deque

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    H = [0] * (N + 1)
    for i in range(1, N + 1):
        H[i] = int(input_data[idx]); idx += 1
    
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        adj[u].append(v)
        adj[v].append(u)
    
    # Binary search on the answer (maximum height threshold)
    # For a given threshold T, check if there's a path from 1 to N
    # using only nodes with H[i] <= T, with path length <= K.
    # We must always include nodes 1 and N, so T >= max(H[1], H[N]).
    
    # Collect all unique heights
    heights = sorted(set(H[1:N+1]))
    
    # We need T >= H[1] and T >= H[N]
    min_required = max(H[1], H[N])
    
    # Filter heights that are >= min_required
    # Binary search over these heights
    candidates = [h for h in heights if h >= min_required]
    
    if not candidates:
        print(-1)
        return
    
    def check(threshold):
        # BFS from node 1 to node N using only nodes with H[i] <= threshold
        # Find shortest path (in terms of number of nodes) and check if <= K
        if H[1] > threshold or H[N] > threshold:
            return False
        
        # BFS
        dist = [0] * (N + 1)  # 0 means unvisited
        dist[1] = 1  # distance in terms of node count
        queue = deque()
        queue.append(1)
        
        while queue:
            u = queue.popleft()
            d = dist[u]
            if u == N:
                return d <= K
            if d >= K:
                continue
            for v in adj[u]:
                if dist[v] == 0 and H[v] <= threshold:
                    dist[v] = d + 1
                    if v == N:
                        return dist[v] <= K
                    queue.append(v)
        
        return False
    
    # Binary search on candidates
    lo, hi = 0, len(candidates) - 1
    
    # First check if the largest candidate works
    if not check(candidates[hi]):
        print(-1)
        return
    
    while lo < hi:
        mid = (lo + hi) // 2
        if check(candidates[mid]):
            hi = mid
        else:
            lo = mid + 1
    
    print(candidates[lo])

solve()

---

この解説は claude4.6opus-thinking によって生成されました。