問題概要
不思議の国の王様は，底の高い靴を履くのが好きである．
不思議の国には 個の町と，それらを結ぶいくつかの道路がある．道路の情報は 3 つの配列
によって表され，
番の道路は，2 つの町
を（双方向に）結んでいて，その高さ制限が
である．高さ制限は，道
を通るとき，履いている靴の底の高さが
以下でなければならないことを表す．
王様は，町 を出発して，町
へ（底の高い靴を履いて徒歩で）行こうとしている．王様は可能な限り底の高い靴を履きたいので，出発の前にいくつか（ 0 個でもよい）の道の高さ制限を緩和させることにした．王様は制限緩和のために
の予算を用意している．ある道の高さ制限を
だけ緩和させるとき，
のコストがかかる．また，1 つの道路に対し制限緩和を行える回数は高々 1 回である．
が与えられる．予算内で町
から町
へ移動するとき，履くことのできる靴底の高さの最大値を求めよ．
解法
露骨にグラフの問題なので，町を頂点，道を辺としたグラフを考えます．また， と書きます．
まず，高さ制限の緩和は出発前ではなく，出発後に適宜行うものと考えても問題がありません．そう考えると，王様の行動は，必要時に費用を支払いながらグラフ上を遷移していくものと見做せます．費用と同時に通行可能な靴底の高さ（＝通った辺の高さ制限の最小値）を求めなければなりません．こういう*1場合，頂点を拡張して ( 頂点番号, 高さの最小値 ) とする拡張グラフ上での探索に置き換えることをよくやりますが，この問題の場合，高さの取り得る値がそれなりに大きいので，この方法は使えません（ なので，TLE も MLE もやばい）．
ここで，高さに関する特徴を利用します．ある靴底の高さ ではコスト
以下での到達が不可能だとします．このとき，高さ
の場合も不可能であることが言えます（高さ
の場合と比べて，制限緩和の量が減ることはない）．また，高さ
での到達が可能だったとすれば，高さ
でも到達可能です．この 2 つの事実及びそれぞれに関する数学的帰納法から，到達可能性は高さに関して単調性をもつことが分かります．
単調性をもつ真偽値関数 について，（
の増加に伴って
が 1 から 0 に変化するならば）
となる最大の
を二分探索により求めることができます．
二分探索により通過する道路の高さ制限の最大値を仮定したとき，各道路について通行のために必要な費用が一意的に定まり，頂点を拡張しないグラフの上で探索をすることができます．かかる費用は当然小さい方がよいので，費用をコストとした重み付きグラフでの最短経路問題に帰着されます．従って，Dijkstra 法などを使ってこの部分問題を解くことで，二分探索のための可能/不可能判定を行うことができます．
この解法は，高さに関する二分探索の中で毎回 Dijkstra 法を実行するので， 時間で実行できます．
コード
using LL = long long; using ULL = unsigned long long; #define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) // Dijstra 法による単一始点最短経路問題ソルバ #include <vector> #include <queue> #include <utility> #include <limits> #include <type_traits> namespace ShortestPath { template < typename DIST_TYPE = int, typename = typename std::enable_if< std::is_arithmetic< DIST_TYPE >::value >::type > class Dijkstra { private: const int V; std::vector< std::vector< std::pair< int, DIST_TYPE > > > G; public: static DIST_TYPE inf() { return std::numeric_limits< DIST_TYPE >::max(); } Dijkstra( const int v ) : V( v ), G( V ) { return; } void connect( const int u, const int v, const DIST_TYPE d ) { G[u].emplace_back( v, d ); return; } std::vector< DIST_TYPE > solve( const int s, const DIST_TYPE d0 = 0 ) { std::vector< DIST_TYPE > distances( V, inf() ); distances[s] = d0; std::priority_queue< std::pair< DIST_TYPE, int >, std::vector< std::pair< DIST_TYPE, int > >, std::greater< std::pair< DIST_TYPE, int > > > que; que.emplace( d0, s ); while ( !que.empty() ) { const DIST_TYPE dist = que.top().first; const int u = que.top().second; que.pop(); if ( distances[u] < dist ) { continue; } for ( auto &e : G[u] ) { const int v = e.first; const DIST_TYPE d = e.second; if ( distances[u] + d < distances[v] ) { que.emplace( distances[v] = distances[u] + d, v ); } } } return distances; } }; } // ShortestPath::Dijkstra( |V| ) // connect( from, to, cost ) // solve( s, d0 = 0 ) class TallShoes { public: int maxHeight( int N, vector <int> X, vector <int> Y, vector <int> height, long long B ) { const int M = X.size(); LL lb = 0, ub = 1000000000; while ( lb + 1 < ub ) { const LL mid = ( lb + ub ) / 2; ShortestPath::Dijkstra< LL > dijksra( N ); REP( i, 0, M ) { const int a = X[i], b = Y[i]; const LL r = mid - height[i]; const LL c = 0 < r ? r * r : 0; dijksra.connect( a, b, c ); dijksra.connect( b, a, c ); } ( dijksra.solve( 0 ).back() <= B ? lb : ub ) = mid; } return lb; } };
