侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【Dijkstra算法】路径【蓝桥杯】

GabrielxD
2023-01-17 / 0 评论 / 0 点赞 / 17 阅读 / 537 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2023-01-17,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

路径 - 蓝桥云课


本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。

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

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

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

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

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

提示:建议使用计算机编程解决问题。

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

解题

方法一:Dijkstra算法

思路

单源最短路问题的裸题,直接用朴素版Dijkstra算法求解即可。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 2021, INF = 0x3f3f3f3f;
    static int[][] g = new int[N + 1][N + 1];

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    static int dijkstra(int ori, int dest) {
        boolean[] vis = new boolean[N + 1];
        int[] dists = new int[N + 1];
        Arrays.fill(dists, INF);
        dists[ori] = 0;
        for (int i = 1; i < N; ++i) {
            int mn = -1;
            for (int j = 1; j <= N; ++j) {
                if (!vis[j] && (mn == -1 || dists[j] < dists[mn])) mn = j;
            }
            vis[mn] = true;
            for (int j = 1; j <= N; ++j) {
                dists[j] = Math.min(dists[j], dists[mn] + g[mn][j]);
            }
        }
        return dists[dest];
    }

    public static void main(String[] args) throws IOException {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (Math.abs(i - j) > 21) g[i][j] = g[j][i] = INF;
                else g[i][j] = g[j][i] = lcm(i, j);
            }
        }
        System.out.println(dijkstra(1, 2021));
    }
}
0

评论区