蓝桥杯：路径

小咪咪 2024-03-25 22:48 12阅读 0赞

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

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

小蓝的图由 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

代码：利用动态规划

import java.util.* ;
    
    public class P4{
        public static void main(String[] args) {
            int []dp=new int[2022];
            for (int i=1;i<2022;i++){
                for (int j=i+1;j<2022&&j-i<=21;j++){
                    if(dp[j]==0){
                        dp[j]=dp[i]+zxg(i,j);
                    }else{
                        dp[j]=Math.min(dp[j],dp[i]+zxg(i,j));
                    }
                }
            }
            System.out.println(dp[2021]);
        }
    
        //最大公约数
        public static int gcd(int a,int b){
            return b==0?a:gcd(b,a%b);
        }
        //最小公倍数
        public static int zxg(int a,int b){
            return a*b/gcd(a,b);
        }
    
    }

![142ad094533f22bac2f20bed994c8e8d.png][]

[142ad094533f22bac2f20bed994c8e8d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7290b397711c475c9ce3ebf2c8c16372.png

发表评论取消回复

表情：

评论列表（有 0 条评论，12人围观）

还没有评论，来说两句吧...

相关阅读

相关蓝桥杯：路径

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。小蓝的图由 20

小咪咪/ 2024年03月25日 22:48/ 0 赞/ 13 阅读

相关蓝桥杯题目

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

分手后的思念是犯贱/ 2023年01月12日 01:52/ 0 赞/ 248 阅读

相关【蓝桥杯】蓝桥杯入门训练+蓝桥杯基础训练

BEGIN-1 A+B问题资源限制时间限制：1.0s 内存限制：256.0MB 问题描述输入A、B，输出A+B。输入格式输入的第一行包括两个

野性酷女/ 2022年12月03日 01:59/ 0 赞/ 390 阅读

相关蓝桥杯奖学金

上一篇博客：[蓝桥杯纪念品分组（贪心，排序）][Link 1] > 写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个

港控/mmm°/ 2022年11月06日 01:56/ 0 赞/ 178 阅读

相关蓝桥杯—排序

2016年第七届第4题快速排序排序在各种场合经常被用到。快速排序是十分常用的高效率的算法。其思想是：先选一个“标尺”，用它把整个队列

﹏ヽ暗。殇╰゛Y/ 2022年06月18日 11:25/ 0 赞/ 278 阅读

相关蓝桥杯

又到了一年一度蓝桥杯，真是烦，不知道要不要参加。去年我报名了，忘了留意时间错过了。今年又大三，想学的又特别多，报名吧得花很多时间准备，可不报名吧，以后简历又不好看。参加的

傷城~/ 2022年05月07日 19:28/ 0 赞/ 318 阅读

相关蓝桥杯

又到了一年一度蓝桥杯，真是烦，不知道要不要参加。去年我报名了，忘了留意时间错过了。今年又大三，想学的又特别多，报名吧得花很多时间准备，可不报名吧，以后简历又不好看。参加的

客官°小女子只卖身不卖艺/ 2022年05月07日 05:54/ 0 赞/ 312 阅读

相关蓝桥杯圆周率

数学发展历史上，圆周率的计算曾有许多有趣甚至是传奇的故事。其中许多方法都涉及无穷级数。图1.png中所示，就是一种用连分数的形式表示的圆周率

浅浅的花香味﹌/ 2022年03月07日 10:44/ 0 赞/ 319 阅读

相关蓝桥杯抽签

抽签 X星球要派出一个5人组成的观察团前往W星。其中： A国最多可以派出4人。 B国最多可以派出2人。 C国最多可以派出2人。 … 那么最终派往W星

短命女/ 2022年03月01日 18:22/ 0 赞/ 319 阅读

相关蓝桥杯国赛——路径（最短路）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

水深无声/ 2021年07月17日 01:34/ 0 赞/ 458 阅读