2021第十二届蓝桥杯省赛真题：路径
发布时间
阅读量：
阅读量
文章目录
-
- 试题 D ：路径
-
- 【问题描述】
- 【思路】
- 【代码】
- 【结果】
- 【做题链接】
试题 D ：路径
类型：结果填空，总分：10分
【问题描述】
小蓝掌握了最短路径算法后感到非常激动，并构造了一个特殊的图结构以寻找其中的最短路径。这个图包含2021个节点依次编号为1至2021对于任意两个不同的节点a和b如果它们之间的差值绝对值超过21则它们之间没有连线；反之如果差值绝对值不超过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);
}
}
java
【结果】
10266837
【做题链接】
水平有限不保证对，欢迎各位大佬评论交流
全部评论 (0)
还没有任何评论哟~