ABC143 E - Travel by Car (500)
公式解説の解法は天才
コンテスト中
Q回の中でダイクストラ法を回すと$ O(N^2)の中でそれぞれ$ O(N^2)なので$ O(N^4)
ワーシャルフロイド法で全点間の最短距離を一発で求めるのも始点によって補給位置が異なるので駄目
距離に補給回数、補給前の距離、補給後の距離を定義して最短距離を求めようとしたが駄目
補給回数が0の時が駄目など
解説を見て
まずワーシャルフロイド法で最短距離を求める
点間の距離がL以下の場合にコスト1の辺を張る
これでもう一度ワーシャルフロイド法を使う
補給位置が最短になるような経路を使って計算される
初回は補給が要らないので1引いた値が実際の補給回数
Q回のクエリではこの結果引っ張ってくるだけ
最短距離が初期値のままの場合、到達不可能なので-1
ダイクストラ法の位置を改善すると
ダイクストラ法は単一の始点から全点への最短距離を求められる
つまりQ回行わなくても、N回のダイクストラ法の実施で済む
すべての点を始点としてそれぞれダイクストラ法を実施する
Q回のクエリではこの結果引っ張ってくるだけ
最短距離が初期値のままの場合、到達不可能なので-1
どちらのアルゴリズムでも$ O(N^3 + Q)
ダイクストラ法を使う場合、オリジナルの$ O(N^2)が計算量が小さくなる
辺の数が$ O(N^2)なので計算量にEが出てくる場合、計算量が上のより大きくなる