二分探索：k 番目の値を最小化（1題）

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
この本（通称：蟻本）の章末で紹介されている練習問題をひたすらといている。

二分探索。k 番目の値を最小化する問題である。

POJ3662: Telephone Lines

3662 -- Telephone Lines

問題概要

N 個の頂点を持つ重み付き無向グラフが与えられる。頂点 1 から頂点 N への経路において、大きい順で K + 1 番目の辺の長さを最小化する問題。

解法

二分探索 + ダイクストラ。
C(x) : K+1 番目の辺の長さが x 以下であるような経路を作れる
C(x) を判定するための時間を見積もる。C(x) は言い換えると「長さ x より大きい辺が K 本以下であるような経路を作れる」ということになる。これを判定するためには、長さ x 以下の辺のコストを 0、長さ x より大きな辺のコストを 1 として、最短コスト K 以下でゴールに到達できるかどうかをみればよい。ダイクストラ法で O(E * log N)。あとは C(x) を満たす最小の x を二分探索で求める。