牛客IOI周赛普及组27 D.旅游(floyd)
旅游
https://ac.nowcoder.com/acm/contest/11234/D
Description
给出一个有向图，提供两种操作：
- 将当前点加入到最短路规划中
- 计算当前点到
的距离
Solution
数据范围满足 ，操作1最多只会执行
次，考虑每次都使用
进行
的任意两点最短路径计算，总体时间复杂度
，那么对于操作2，每次只需要
判断并输出答案即可。
注意到 的遍历特点：
for k in [1, n]:
for i in [1, n]:
for j in [1, n]:
Graph[i][j] = min(Graph[i][j], Graph[i][k] + Graph[k][j] 最外层的 作为中转点进行松弛，在这里我们把某个点加入到最短路规划中，实际上就是添加这么一个中转点。
