第十二届蓝桥杯 JavaA组 试题D 路径 Floyd算法

答案：10266837

public class Main {
    public static void main(String[] args) {

        int n = 2022;
        int INF = 0x3f3f3f3f;
        int[][] map = new int[n][n];
        //初始化图
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = INF;
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j < n && j <= i + 21; j++) {
                if (j > 0) {
                    map[i][j] = map[j][i] = lcm(i,j);
                }
            }
        }
        // 记录路径path
        String[][] path = new String[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                path[i][j]="";
            }
        }
        //核心代码(三个for循环)
        for (int k = 1; k < n; k++) {
            for (int i = 1; i < n; i++) {
                for (int j = 1; j < n; j++) {
                    if (map[i][k] + map[k][j] < map[i][j]) {
                        map[i][j] = map[i][k] + map[k][j];
                        path[i][j] = path[i][k] + k +"->"+ path[k][j];
                    }
                }
            }
        }
        System.out.println(map[1][2021]);
    }
    //最大公约数
    public static int gcd(int a, int b) {
        if (a == 0 || b == 0)
            return 0;
        return a % b == 0 ? b : gcd(b, a % b);
    }
    //最小公倍数
    public static int lcm(int a, int b) {
        int gc = gcd(a, b);
        return a * b / gc;
    }
}