7K12 blog

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

ABC012 D - バスと避けられない運命

f:id:tkr987:20200716233747p:plain

https://atcoder.jp/contests/abc012/submissions/10345521

  • max(始点v[i]から目的地v[j]への最短経路)がminになるバス停v[i]を見つける
  • つまり全点対間最短経路を求めればok

f:id:tkr987:20200717004334p:plain
最大値の最小値が答え。つまりバス停 V_iについて、 V_0に引っ越した時の最大値、 V_1に引っ越した時の最大値、…、 V_{N-1}に引っ越した時の最大値、のうち最小値になる。制約から O(N^3)が許されるので、全点対間最短経路をワーシャルフロイド法で求めれば答えが分かる。

注意点として辿り着けないバス停はないが、バス停 V_iから V_iのような距離がワーシャルフロイド法ではinfになっているので、infを0にする後処理をしておく。