2021第十二届蓝桥杯省赛真题：路径

试题 D ：路径

【问题描述】【思路】【代码】【结果】【做题链接】

类型：结果填空，总分：10分

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点
之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。

最短路径模板题，直接用朴素Dijkstra就行，挖坑俺有空再总结一下最短路算法注意图的构造，求最大公约数和最小公倍数老熟人了发现另一种思路大佬的dp做法错误记录：在用邻接矩阵存图的时候，我们一般会用一个自定义的无穷大的数代表两点之间不连通，c/c++中一般会写memset(dist, 0x3f, sizeof dist);，我一开始考虑用Java的Integer.MAX_VALUE代表无穷大，但是我忽略了这样就不能计算了，因为Integer.MAX_VALUE随便加上一个数就超出int的表示范围结果就成负数（补码）了，所以注意无穷大还是得用static final int INF = 0x3f3f3f3f;。0x3f3f3f3f的优点有：十进制为1061109567，和Integer.MAX_VALUE一个数量级，即10^9数量级，而一般场合下的数据都是小于10^9的。 0x3f3f3f3f * 2 = 2122219134，我们定义的这个无穷大相加依然不会溢出。

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    static final int INF = 0x3f3f3f3f;
    static final int N = 2030;
    static int[][] g = new int[N][N];
    static int[] dist = new int[N];
    static boolean[] s = new boolean[N];
    public static void main(String[] args) {
        //初始化图和距离
        for(int i = 1; i <= 2021; i++) {
            for(int j = i; j <= 2021; j++) {
                if(j - i > 21) {
                    g[i][j] = g[j][i] = INF;
                } else {
                    g[i][j] = g[j][i] = lcm(i, j);
                }
            }
        }
        Arrays.fill(dist, INF);
        dist[1] = 0;

        //朴素DijKstra
        for(int i = 1; i <= 2021; i++) {
            int v = -1;
            for(int j = 1; j <= 2021; j++) {
                if(!s[j] && (v == -1 || dist[v] > dist[j])) {
                    v = j;
                }
            }
            s[v] = true;
            for(int j = 1; j <= 2021; j++) {
                dist[j] = Math.min(dist[j], dist[v] + g[v][j]);
            }
        }

        System.out.println(dist[2021]);
    }
    
    //求最大公约数
    public static int gcd(int a, int b) {
        //递归方式性能差些，但是写法简单
        //return b == 0 ? a : gcd(b, a % b);
        int t;
        while(b != 0) {
            t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
    //求最小公倍数
    public static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
}

10266837

https://www.lanqiao.cn/problems/1460/learning/

水平有限不保证对，欢迎各位大佬评论交流