Floyd 算法

思路：本题是多源最短路问题，使用Floyd算法求解。Floyd 算法对边的权值正负没有要求，核心思想是动态规划。
我们使用动规五部曲来理解和应用Floyd算法：

1、确定dp数组（dp table）以及下标的含义
我们用 grid数组来存图，那就把dp数组命名为 grid。grid[i][j][k] = m，表示 节点i 到 节点j 以[1…k] 集合为中间节点的最短距离为m。

2、确定递推公式
分两种情况：
（1）节点i 到 节点j 的最短路径经过节点k：grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]
（2）节点i 到 节点j 的最短路径不经过节点k：grid[i][j][k] = grid[i][j][k - 1]
因为求最短路，取两种情况的最小值： grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])

3、dp数组初始化
在开始输入边时不经过其他节点，可以把k 赋值为 0，即grid[i][j][0]。同时，本题求的是最小值，grid数组中其他元素数值应该初始为一个最大数。

4、确定遍历顺序
从递推公式：grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1]) 可以看出，我们需要三个for循环，分别遍历i，j 和k。我们把 k =0 的 i 和j 对应的数值都初始化了，再去计算 k = 1 时 i 和 j 对应的数值。这就好比是一个三维坐标，i 和j 是平层，而k 是 垂直向上 的。遍历的顺序是从底向上 一层一层去遍历。所以遍历k 的for循环一定是在最外面。

5、举例推导dp数组

代码如下：

import java.util.*;
public class Main{
    public static void main (String[] args) {
        Scanner scan =new Scanner(System.in);
        int n=scan.nextInt();
        int m=scan.nextInt();
        int[][][] grid=new int[n+1][n+1][n+1];
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                Arrays.fill(grid[i][j],Integer.MAX_VALUE);
            }
        }
        //添加边的权重，初始化
        for(int i=0;i<m;i++){
            int l=scan.nextInt();
            int r=scan.nextInt();
            int val=scan.nextInt();
            grid[l][r][0]=val;
            grid[r][l][0]=val;
        }
        
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if (grid[i][k][k - 1] != Integer.MAX_VALUE && grid[k][j][k - 1] != Integer.MAX_VALUE) {
                        grid[i][j][k] = Math.min(grid[i][k][k - 1] + grid[k][j][k - 1], grid[i][j][k - 1]);
                    } else {
                        grid[i][j][k] = grid[i][j][k - 1];
                    }
                }
            }
        }
        
        int num=scan.nextInt();
        while(num>0){
            int start=scan.nextInt();
            int end=scan.nextInt();
            num--;
            if(grid[start][end][n]==Integer.MAX_VALUE) System.out.println(-1);
            else System.out.println(grid[start][end][n]);
        }
    }
}

注意：当两个 Integer.MAX_VALUE 值相加时，会导致整数溢出，结果会变成一个非常小的负数，如 -128。