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]
最外层的 作为中转点进行松弛,在这里我们把某个点加入到最短路规划中,实际上就是添加这么一个中转点。