2021蓝桥杯 java路径

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。

小蓝的图由 2021 个结点组成，依次编号 1 至 2021。

对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。

例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。

请计算，结点 1 和结点 2021 之间的最短路径长度是多少。

public class Main {

    static final int n = 2021;
    //求ab之间的最小公约数
    static int gcd(int a,int b){
        return b == 0 ? a : gcd(b,a%b);
    }
    //求ab之间的最小公倍数
    static int lcm(int a,int b){
        return a * b / gcd(a,b);
    }

    public static void main(String[] args) {
        //记录两点之间的边长，初始值都为零，如果数组某点未变化则说明两点之间没有边长
        int[][] floyd = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n && j < i+22 ; j++) {
                //根据题意可知两点之间的边长相等且等于最小公倍数，如果两点之间的差值大于21，两点间没有边长
                floyd[i][j] = floyd[j][i] = lcm(i+1,j+1);
            }
        }
        //弗洛伊德算法
        for (int k = 0; k < n; k++) {
            //中介点为k
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    //（i和k、k和j之间的边长不为零且（i和j之间没有边长或者通过中介点k，i到k，k到j的距离之和小于i到j的距离））成立则替换i到j的距离
                    if(floyd[i][k] != 0 && floyd[k][j] != 0 && (floyd[i][j] == 0 || floyd[i][k] + floyd[k][j] < floyd[i][j]))
                        floyd[i][j] = floyd[i][k] + floyd[k][j];
                }
            }
        }
        //经过循环后，找出数组存储1到点2021之间的数据，该数据则为最短距离。
        System.out.println(floyd[0][n-1]);
    }
}