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

链接