ABC160 D - Line++ - 7K12 blog

f:id:tkr987:20200625204825p:plain

https://atcoder.jp/contests/abc160/submissions/11321133

ダイクストラ法は単一始点から全ての終点までの最短経路を求める
ダイクストラ法は $O( (V+E) \log V )$

f:id:tkr987:20200625210620p:plain

基本的に $V_{i}$ と $V_{i+1}$ にしか辺が存在せず、それとは別に追加される辺が1本しかない。そのため、辺の本数が頂点数と殆ど同じという特徴がある。頂点数の制約が $10^3$ と小さいので、多項式時間 $O(N^2)$ までの処理が許される。ダイクストラ法を使えば単一始点から全ての終点までの最短経路が $O( (V+E) \log V )$ で分かるので、全ての始点に対してダイクストラ法をV回使っても $O(V^2)$ 程度に収まる。正確には全体計算量は $O( (V+E)^2 \log^2 V )$ となる。