https://atcoder.jp/contests/abc012/submissions/10345521
- max(始点v[i]から目的地v[j]への最短経路)がminになるバス停v[i]を見つける
- つまり全点対間最短経路を求めればok
最大値の最小値が答え。つまりバス停について、
に引っ越した時の最大値、
に引っ越した時の最大値、…、
に引っ越した時の最大値、のうち最小値になる。制約から
が許されるので、全点対間最短経路をワーシャルフロイド法で求めれば答えが分かる。
注意点として辿り着けないバス停はないが、バス停から
のような距離がワーシャルフロイド法ではinfになっているので、infを0にする後処理をしておく。
