第十二届蓝桥杯省赛JavaB组试题 E:路径

待我称王封你为后i 2023-01-13 14:52 35阅读 0赞

## 试题 E: 路径 ##

本题总分：15 分

### 【问题描述】 ###

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

### 【答案提交】 ###

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分

#### 答案 ####

10266837

### 代码 ###

public class Main { 
    
    	public static void main(String[] args) { 
    		int[] f = new int[2050];
    		for (int i = 2; i <= 2021; i++) { 
    			for (int j = i + 1; j <= i + 21; j++) { 
    				if (f[j] == 0) { 
    					f[j] = f[i] + lcm(i, j);
    				} else { 
    					f[j] = Math.min(f[j], f[i] + lcm(i, j));
    				}
    			}
    		}
    		System.out.println(f[2021]);
    	}
    
    	private static int lcm(int a, int b) { 
    		int t = 1;
    		while (b * t % a != 0) { 
    			t++;
    		}
    		return t * b;
    	}
    
    }

发表评论取消回复

表情：

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

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

相关阅读

相关第十三届蓝桥杯JavaB组国赛E题——迷宫 (AC)

目录 1.迷宫 1.问题描述 2.输入格式 3.输出格式 4.样例输入 5.样例输出

亦凉/ 2023年09月28日 23:19/ 0 赞/ 64 阅读

相关第十四届蓝桥杯大赛软件赛省赛JavaB组解析

目录说在前面试题 A: 阶乘求和代码：题目分析：试题 B: 幸运数字代码：题目分析：试题 D: 矩形总面积代码：题目分析：试题 G:

╰+攻爆jí腚メ/ 2023年09月27日 17:13/ 0 赞/ 147 阅读

相关第十二届蓝桥杯省赛第一场B组

A：ASC（Java） 76 A：空间（C++） 67108864 B：卡片 3181 C：直线 40257

短命女/ 2023年01月17日 14:53/ 0 赞/ 161 阅读

相关第十二届蓝桥杯省赛JavaB组试题 G: 最少砝码

【问题描述】你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。那么这套砝码最少需要包含多少个砝码？

深藏阁楼爱情的钟/ 2023年01月15日 14:21/ 0 赞/ 148 阅读

相关第十二届蓝桥杯省赛JavaB组试题 E:路径

试题 E: 路径本题总分：15 分【问题描述】小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。小蓝的图由

待我称王封你为后i/ 2023年01月13日 14:52/ 0 赞/ 36 阅读

相关 2017 蓝桥杯 JavaB组省赛

> 2018年4月1日，备战2018蓝桥杯省赛！ > 转载请注明出处[https://blog.csdn.net/yuanlaijike/article/details/6

朴灿烈づ我的快乐病毒、/ 2022年07月03日 14:27/ 0 赞/ 341 阅读

相关 2014 蓝桥杯 JavaB组省赛

1. 武功秘籍 2. 切面条 3. 猜字母 4. 大衍数列 5. 圆周

深碍√TFBOYSˉ_/ 2022年06月18日 12:16/ 0 赞/ 261 阅读

相关 2015 蓝桥杯 JavaB组省赛

1. 三角形面积 2. 立方变自身 3. 三羊献瑞 4. 循环节 5.

忘是亡心i/ 2022年06月18日 10:49/ 0 赞/ 276 阅读

相关 2016 蓝桥杯 JavaB组省赛

> 2018年4月1日，备战2018蓝桥杯省赛！ > 转载请注明出处[https://blog.csdn.net/yuanlaijike/article/details/6

- 日理万妓/ 2022年06月18日 10:43/ 0 赞/ 308 阅读

相关第十届蓝桥杯省赛

这是个悲伤的故事今天，第十届蓝桥杯比赛成绩公布了，我是第一次参加蓝桥杯（校内选拔不算），个人觉得，这次比赛的题目大都不难，甚至有部分真的太容易了，　　但是我的成绩

Dear 丶/ 2022年02月26日 13:42/ 0 赞/ 365 阅读