题解：AT_joi2020ho_d オリンピックバス (Olympic Bus)

QwQrryble · 2026-07-24 09:42:46 · 题解

不难的题。

发现 n 很小，考虑 O(n^3) 的做法。

考虑一个性质：最短路最多只会经过 n 条边。于是考虑枚举所有边，如果这条边在最短路上就暴力重新跑，否则就直接用原来的最短路计算比较即可。

最短路跑暴力 dij，时间复杂度 O(n^3+m)。