概要

地点 \(1\) から地点 \(N\) まで所要時間 \(T\) 以下で移動するとき、経路上で訪れる地点の危険度の最大値を最小化する問題です。二分探索 + ダイクストラ法で解くことができます。

考察

まず、求めたいのは「経路上の地点の危険度の最大値の最小値」です。このように 「最大値を最小化する」 という形の問題は、二分探索（パラメトリックサーチ） と相性が良いことが知られています。

単調性に注目する

ある危険度の閾値 \(X\) を固定して、次のような判定問題を考えます。

危険度が \(X\) 以下の地点だけを通って、地点 \(1\) から地点 \(N\) まで所要時間 \(T\) 以下で到達できるか？

ここで重要なのは、この判定問題には 単調性 があるということです。

• もし閾値 \(X\) で到達可能なら、\(X\) より大きい閾値 \(X'\) でも当然到達可能（通れる地点が増えるだけなので）。
• 逆に \(X\) で到達不可能なら、\(X\) より小さい閾値では当然不可能。

つまり、ある境界値を境にして「不可能 → 可能」と切り替わります。この境界値こそが求める答えです。

判定問題の解き方

閾値 \(X\) を固定したとき、「危険度が \(X\) 以下の地点のみを使える」という制約のもとで、地点 \(1\) から地点 \(N\) までの最短時間を求めれば、それが \(T\) 以下かどうかで判定できます。最短経路は ダイクストラ法 で求められます。

注意点として、地点 \(1\) や地点 \(N\) 自身の危険度が \(X\) を超える場合は、そもそもスタートもゴールも使えないので不可能です。これは答えの候補を \(\max(P_1, P_N)\) 以上に限定することで自然に扱えます。

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

危険度のすべての値を小さい順に試して最初に到達可能になる値を探す、という線形探索でも正しい答えは出ますが、危険度の候補が最大 \(N\) 種類あり、それぞれでダイクストラ法（\(O(M \log N)\)）を実行すると \(O(N \cdot M \log N)\) となり、\(N, M\) が大きい場合に間に合いません。

そこで、単調性を利用した 二分探索 により、判定問題を呼び出す回数を \(O(\log N)\) 回に削減します。

アルゴリズム

1. 危険度の候補値を準備する。答えとなりうる値は地点の危険度 \(P_i\) のいずれかなので、\(\max(P_1, P_N)\) 以上の \(P_i\) を重複を除いてソートしておく。
2. 候補値の配列に対して二分探索を行う。中央の候補値 \(X\) について、判定問題（危険度 \(X\) 以下の地点のみで \(T\) 以下で到達可能か）をダイクストラ法で解く。
   • 到達可能なら、より小さい候補値を試す（答えを更新）。
   • 到達不可能なら、より大きい候補値を試す。
3. 最終的に到達可能となる最小の候補値が答え。

判定（ダイクストラ法）の詳細

• 各地点 \(i\) について「危険度 \(P_i \le X\)」のときだけ訪問を許可する。
• スタート（地点 \(1\)）から各地点への最短時間を求め、地点 \(N\) への最短時間が \(T\) 以下かを判定する。
• 実装上は、隣接頂点 \(v\) に遷移する際に \(P_v \le X\) をチェックすればよい（スタート地点 \(1\) は候補の下限により保証される）。

計算量

候補値の種類数を \(K\)（高々 \(N\)）とすると、

• 時間計算量: \(O(M \log N \cdot \log K) = O(M \log^2 N)\)
  • ダイクストラ法 1 回が \(O(M \log N)\)、二分探索で \(O(\log K)\) 回呼び出す。
• 空間計算量: \(O(N + M)\)
  • 隣接リストと距離配列を保持する。

\(N \le 2 \times 10^4\), \(M \le 4 \times 10^4\) なので十分高速です。

実装のポイント

• 候補値の下限: スタート地点とゴール地点は必ず通るため、答えは必ず \(\max(P_1, P_N)\) 以上になります。候補値をこの値以上に絞っておくことで、スタート・ゴールが使えないケースを排除でき、ダイクストラ内でのチェックも簡潔になります。

• ダイクストラの早期終了: ゴール地点 \(N\) をヒープから取り出した時点でその距離が確定するため、そこで判定して打ち切ると効率的です。

• 多重辺への対応: 同じ 2 地点を結ぶ複数の登山道が存在し得ますが、隣接リストにそのまま全部追加すればダイクストラ法は正しく動作します。

• 答えの存在保証: 問題の制約により \(T\) 以下で到達できる経路が必ず存在するため、二分探索の上端（最大の候補値）では必ず到達可能であり、答えが見つからないことはありません。

  ソースコード

import sys, heapq

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx+=1
    M = int(data[idx]); idx+=1
    T = int(data[idx]); idx+=1
    P = [0]*N
    for i in range(N):
        P[i] = int(data[idx]); idx+=1
    
    # adjacency
    head = [[] for _ in range(N)]
    for _ in range(M):
        u = int(data[idx])-1; idx+=1
        v = int(data[idx])-1; idx+=1
        w = int(data[idx]); idx+=1
        head[u].append((v,w))
        head[v].append((u,w))
    
    INF = float('inf')
    target = N-1
    
    def feasible(X):
        # vertices with P[i] <= X allowed
        dist = [INF]*N
        dist[0] = 0
        heap = [(0,0)]
        while heap:
            d,u = heapq.heappop(heap)
            if d > dist[u]:
                continue
            if u == target:
                return d <= T
            for v,w in head[u]:
                if P[v] <= X:
                    nd = d + w
                    if nd < dist[v]:
                        dist[v] = nd
                        heapq.heappush(heap,(nd,v))
        return dist[target] <= T
    
    lo = P[0] if P[0] > P[target] else P[target]
    # candidate values: distinct P values >= lo
    cands = sorted(set(p for p in P if p >= lo))
    
    # binary search smallest cands[i] feasible
    left = 0
    right = len(cands)-1
    ans = cands[right]
    while left <= right:
        mid = (left+right)//2
        if feasible(cands[mid]):
            ans = cands[mid]
            right = mid-1
        else:
            left = mid+1
    
    sys.stdout.write(str(ans)+"\n")

main()

---

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