7K12 blog

猫でも分かるアルゴリズム解説

ABC160 D - Line++

f:id:tkr987:20200625204825p:plain

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

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 )となる。