牛客IOI周赛普及组27 D.旅游(floyd)

Description

给出一个有向图，提供两种操作：

1. 将当前点加入到最短路规划中
2. 计算当前点到 的距离

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]

最外层的 作为中转点进行松弛，在这里我们把某个点加入到最短路规划中，实际上就是添加这么一个中转点。

Code

链接