蓝桥杯2021省赛填空题最后一题：
/**
- 小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
-
- 对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；
- 如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
- 请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
- 例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
-
*/
其中无非就是考察两个知识点： 一个是 最小公倍数一个是图的单源路径
这里使用迪杰斯特拉给出邻接矩阵和邻接表的两种形式：
public class 迪杰斯特拉邻接矩阵 {
private static int[][] vetex;// 邻接矩阵
private static final int MAX = Integer.MAX_VALUE;
//这个开始的sn是说从哪个结点开始 dist[i]数组存储的是从sn出发到i结点最短的距离
public static void test(int sn, int dist[]) {
// 初始化访问标记数组
boolean[] flag = new boolean[vetex.length];
flag[sn] = true;
// 为 0 就是不通！
for (int i = 1; i < vetex.length; i++) {
dist[i] = vetex[sn][i]; // 初始化dist数组
}
// 遍历前 找到最小的距离 并且置位
// 遍历 length -1 次就可以了
int num = 1;
// 截止目前 已经有一个设置为访问过了，并且标记为 true了
for (int i = 2; i < flag.length; i++) {
// 再找当前的最小的 所以初始值为 max
int min = MAX;
// 这个地方从1开始是因为我数组存的就是 从1 开始到 2021 （说的是索引）
for (int j = 1; j < dist.length; j++) {
if (!flag[j] && dist[j] != 0 && min > dist[j]) {
min = dist[j];
num = j;
}
}
flag[num] = true;
// 更新 dist数组
for (int j = 1; j < dist.length && min != MAX; j++) {
int tmp = dist[num] + vetex[num][j];
// 开始没写出来就是毁到了这个条件上，老是写错！
if (!flag[j] && vetex[num][j] != 0) {
if (dist[j] == 0 || dist[j] > tmp) {
dist[j] = tmp;
}
}
}
}
System.out.println("final: " + dist[2021]);
}
// 求最大公因数比较简单的一个方法 最小公倍数 = a*b / 最大公因数
public static int gbc(int a, int b) {
return b == 0 ? a : gbc(b, a % b);
}
public static void main(String[] args) {
test2();
}
public static void test2() {
vetex = new int[2022][2022];
for (int i = 1; i < 2022; i++) {
int min = Math.max(i - 21, 1);
for (int j = min; j <= i; j++) {
int div = gbc(i, j);
int lcm = j * i / div;
vetex[j][i] = lcm;
vetex[i][j] = lcm;
}
}
test(1, new int[2022]);
}
}
邻接表：
public class 迪杰斯特拉Queue {
static class Edge {
int curr, length;
// curr 为将要到达的点的编号，length 到达点的为路径长度
Edge(int _curr, int _length) {
curr = _curr;
length = _length;
}
}
static List<Edge>[] graph;
static final int INF = 0x3f3f3f3f; //最大的int值
// 利用PriorityQueue 就是 不用自己进行排序了，他会自动根据我们的设置排序
private static int dijkstra(int st, int ed) {
// 新建小根堆
PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.length, b.length));
boolean[] vis = new boolean[2050];
int[] dist = new int[2050];
Arrays.fill(dist, INF);
dist[st] = 0;
// curr 为将要到达的点的编号，length 到达点的为路径长度
pq.offer(new Edge(st, dist[st]));
while (!pq.isEmpty()) {
int curr = pq.poll().curr;
if (vis[curr]) {
continue;
}
vis[curr] = true;
// 松弛操作 也就是 进行了 重新距离的更新 跟用邻接矩阵做的动作是一样的
for (Edge next : graph[curr]) {
int x = next.curr, len = next.length;
if (dist[x] > dist[curr] + len) {
dist[x] = dist[curr] + len;
pq.offer(new Edge(x, dist[x])); //只是将各个选择走的，路径比较小的 加入 pq，（通过dist进行的比较）
}
}
}
return dist[ed];
}
private static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) {
graph = new List[2050];
// 构建邻接表，每个结点都被放完全了 比如 1中有 21,21中也有1
for (int i = 1; i <= 2021; i++) {
// 这也就是能让每个j 的开始位置为 距离其最远的 那个点
int st = Math.max(i - 21, 1);
for (int j = st; j <= i; j++) {
int div = gcd(j, i);
int lcm = i * j / div;
if (graph[i] == null) {
graph[i] = new ArrayList<>();
}
if (graph[j] == null) {
graph[j] = new ArrayList<>();
}
graph[i].add(new Edge(j, lcm));
graph[j].add(new Edge(i, lcm));
}
}
System.out.println(dijkstra(1, 2021)); // 10266837
}
}
