Readme

2642.Design-Graph-With-Shortest-Path-Calculator

根据题意，我们要时刻准备返回任意两点之间的最短路径，因此Dijkstra算法是不行的。除此之外，想求任意两点之间的最短路径，最经典的算法就是Floyd算法了，而o(N^3)的时间复杂度也是可以接受的。所以我们用Floyd预处理这个图，代码非常优雅

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }

特别注意k必须放在最外层。从形式上看，本质上这就是一个动态规划。

当我们新增一条从a->b的edge时，会对已有网络的最短路径产生什么影响呢？很显然，dp[i][j]无非就两种情况：经过edge，不经过edge。对于前者，我们只需要考察dp[i][a]+edge+dp[b][j]；对于后者，依然还是dp[i][j]。两者取小，就是更新后的dp[i][j].所以我们能用N^2的时间更新所有的dp[i][j]，这也是符合数据量的。

综上，我们可以实时输出dp[i][j]表示两点之间的最短距离。