code_festival_morning_easy_c
考えたこと
sからtへの最短経路であって、途中の頂点でちょうど距離の半分になるようなものが存在するかどうかという問題
最短経路は指数的オーダーで存在するので列挙してから調べることはできない
まずs,tの距離を求めてからその半分の頂点があるか調べよう
ダイクストラ法でs,tの距離を求めた時、それより短い頂点への距離は特定済み
そこからちょうど半分の距離のものを選ぶ
これは最悪N個近く存在する
t,sの距離も同様に求める、かと
d(s,v)=d(t,v)=d(s,t)/2であるようなvがあるかを調べれば良い
これは線形オーダー
計算量はダイクストラ法のものなので間に合う
公式解説
なし
Related Pages
- →chokudai×貪欲法の証明パターン×選択肢が少ない方から貪欲×マトロイド×クラスカル法×区間スケジューリング×交換しても悪化しない×アルゴリズムとデータ構造×区間はマトロイドではない×abc076b×現在が良いほど未来も良い×poj3617×poj3069×ダイクストラ法×agc009a×arc111×abc187×arc110c×一回り小さい同じ形の問題×agc049b×abc103d×abc023d×和の比率の最大化×単位時間ジョブスケジューリング問題×乱択＋貪欲×abc171_f×離散凸性→
- →past5×past202012×アルゴリズム実技検定×past過去問練習202012×past5e×past5f×past5g×past5h×PAST5I×past5j×past5k×past5l×past5m×past5n×past5o×番兵×地図読み込み時に番兵をつける×ゴールをスタートにする×ゴールを一つにする×ダイクストラ法×bit_dp×期待値dp×二次元の片方を時間軸にする×past2n→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]