``` import java.util.Arrays; public class 路径 { static final int MAX_NODE = 2021; // 定义常量MAX_NODE，表示图中的最大节点数 static final long INF = Long.MAX_VALUE; // 定义常量INF，表示无穷大，用于初始化距离数组 // 方法：计算两数的最大公约数（GCD） private static long gcd(long a, long b) { if (b == 0) return a; // 递归的基本情况，当b为0时返回a return gcd(b, a % b); // 使用欧几里得算法递归计算GCD } // 方法：计算两数的最小公倍数（LCM） private static long lcm(long a, long b) { return (a / gcd(a, b)) * b; // 计算最小公倍数：乘积除以最大公约数 } // 使用Dijkstra算法计算从节点1到节点2021的最短路径 public static long findShortestPath() { // distances数组，存储从源点到每个点的最短距离 long[] distances = new long[MAX_NODE + 1]; // 创建距离数组，大小为MAX_NODE + 1 Arrays.fill(distances, INF); // 初始化所有距离为无穷大 distances[1] = 0; // 将起点到自身的距离设置为0 boolean[] visited = new boolean[MAX_NODE + 1]; // 创建一个标记数组，用于记录节点是否已访问 for (int i = 0; i < MAX_NODE; i++) { // 遍历所有节点 // 找到当前未访问的距离最小的节点 long minDistance = INF; int minIndex = -1; for (int j = 1; j <= MAX_NODE; j++) { if (!visited[j] && distances[j] < minDistance) { minDistance = distances[j]; minIndex = j; } } if (minIndex == -1) break; // 所有可达节点都访问过了，则退出循环 visited[minIndex] = true; // 标记当前节点为已访问 // 更新当前节点相邻节点的距离 for (int j = 1; j <= MAX_NODE; j++) { // 遍历所有节点 if (Math.abs(minIndex - j) <= 21) { // 如果节点间差的绝对值小于等于21 long edgeWeight = lcm(minIndex, j); // 计算这两个节点之间边的权重（最小公倍数） if (!visited[j] && distances[j] > distances[minIndex] + edgeWeight) { distances[j] = distances[minIndex] + edgeWeight; // 更新最短距离 } } } } return distances[MAX_NODE]; // 返回从节点1到节点2021的最短路径长度 } public static void main(String[] args) { // 主函数 System.out.println(findShortestPath()); // 调用findShortestPath方法并打印结果 } } ```

最短路的模板 ```python import math import heapq n = 2021 g = [[0] * (n + 1) for _ in range(n + 1)] def lcm(x, y): return x * y // math.gcd(x, y) for i in range(1, n + 1): # 初始化 for j in range(1, n + 1): if abs(i - j) <= 21: w = lcm(i, j) g[i][j] = w g[j][i] = w st = [0] * (n + 1) dist = [math.inf] * (n + 1) # 初始化为inf heap = [] def dijkstra(): dist[1] = 0 heapq.heappush(heap, (0, 1)) while heap: (d, v) = heapq.heappop(heap) if st[v]: continue st[v] = 1 for i in range(1, n + 1): if g[v][i]: if dist[i] > dist[v] + g[v][i]: dist[i] = dist[v] + g[v][i] heapq.heappush(heap, (dist[i], i)) print(dist[2021]) dijkstra() ```

include using namespace std; define ll long long int a[2050][2050]; int d[2025]; int gcd(int a,int b) { ``` return b==0?a:gcd(b,a%b); ``` } int lcm(int a,int b) { ``` return a/gcd(a,b)\*b; ``` } int main() { ``` //ios::sync\_with\_stdio(false),cout.tie(0),cin.tie(0); ``` int n=2021; memset(a,0x3f,sizeof a); memset(d,0x3f,sizeof d); for(int i=1;i<=2021;i++) { ``` a[i][i]=0; for(int j=i+1;j<=i+21&&j<=2021;j++) { a[i][j]=a[j][i]=lcm(i,j); } ``` } d[1]=0; for(int i=1;i<=n;i++) { ``` for(int j=i+1;j<=2021&j-i<=2021;j++) { d[j]=min(d[j],d[i]+a[i][j]); } ``` } cout<<d[2021]; return 0; }

java版本 ```package import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; public class dijkstra { static int N = 2023; static int INF = 0x3f3f3f3f; static int[][]g = new int[N][N]; static int []dist = new int[N]; static boolean[]flag = new boolean[N]; static int n,m; //顶点和边数 static int gcd(int a,int b) { return b==0?a:gcd(b, a%b); } static class Node implements Comparable<Node>{ int v,dis; //节点的权值 public Node(int idx, int i) { // TODO Auto-generated constructor stub this.v=idx; this.dis=i; } @Override public int compareTo(Node o) { // TODO Auto-generated method stub return this.dis-o.dis; } } //idx 为源点 public static void dij(int idx) { PriorityQueue<Node> queue= new PriorityQueue<>(); Arrays.fill(dist, 0,n+1,INF); Arrays.fill(flag, false); dist[idx]=0; queue.offer(new Node(idx,0)); while(!queue.isEmpty()) { Node cur = queue.poll(); int t = cur.v; if(flag[t]) continue; flag[t]=true; //该节点未被遍历 for (int j = 1; j <= n; j++) { if(flag[j]==false&&dist[j]>dist[t]+g[t][j]) { dist[j]=dist[t]+g[t][j]; //只要是大于当前距离的都放进去 queue.offer(new Node(j,dist[j])); } } } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); //初始化邻接矩阵 for (int i = 0; i <=n; i++) { Arrays.fill(g[i], INF); //对于自己 距离为0 g[i][i]=0; } //输入边 // for (int i = 0; i < m; i++) { // int u = scanner.nextInt(); // int v = scanner.nextInt(); // int w = scanner.nextInt(); // g[u][v]=Math.min(g[u][v], w); // } for (int i = 1; i <= 2021; i++) { for (int j = 1; j <= 2021; j++) { if(Math.abs(i-j)>21) { g[i][j]=INF; }else { int gong = i/gcd(i, j)*j; g[i][j]=gong; } } } int st =1; dij(st); if(dist[n] == INF) { System.out.println(-1); // 到达不了终点 } else { System.out.println(dist[n]); // 输出源点1到终点n的最短路径 } } } ```

模板暴力解法，用时70s ``` #include <bits/stdc++.h> #include <windows.h> using namespace std; #define int long long #define endl '\n' vector<vector<int>>graph; const int inf = 1e18; void creategraph(int n){ graph = vector<vector<int>>(n+1,vector<int>(n+1)); for(int i=1;i<n+1;i++){ for(int j=1;j<n+1;j++){ if(i==j){ graph[i][j] = 0; } else{ graph[i][j] = inf; } } } } void addedge(int start,int end,int count){ graph[start][end] = min(graph[start][end],count); graph[end][start] = min(graph[end][start],count); } int getmax(int a,int b){ while(b){ int temp = b; b = a%b; a = temp; } return a; } int getnum(int a,int b){ int num = abs(a-b); if(num>21){ return inf; } return a/getmax(a,b)*b; } signed main(){ creategraph(2021); for(int i=1;i<=2021;i++){ for(int j=i;j<=2021;j++){ int num = getnum(i,j); // cout<<i<<" "<<j<<" "; // cout<<num<<endl; // Sleep(1000); addedge(i,j,num); } } for(int k=1;k<=2021;k++){ for(int i=1;i<=2021;i++){ for(int j=1;j<=2021;j++){ graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j]); // cout<<graph[i][j]<<endl; } } } cout<<graph[1][2021]; return 0; } ```

c++版本 ```cpp #include <cstdio> #include <iostream> #include <algorithm> #include <utility> #include <queue> #include <map> #include <set> #include <vector> #include <tuple> #include <functional> #include <unordered_set> #include <unordered_map> #include <list> #include <cmath> using namespace std; using ll = long long; const int inf = 1e9; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main() { int n = 2021; vector<vector<pair<int, int>>> G(n); for (int i = 0; i < n; ++i) { for (int j = i - 21 < 0 ? 0 : i - 21; j < i; ++j) { // 最小公倍数 = a * b / (a、b的最大公约数) int w = (i + 1) * (j + 1) / gcd(i + 1, j + 1); // 注意 i j 要映射回去编号, 我之前拿下标, 调试了十几分钟才找到八嘎.. G[i].push_back(make_pair(j, w)); G[j].push_back(make_pair(i, w)); } } // 堆优化的迪加斯特拉算法 vector<ll> dis(n, inf); priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; dis[0] = 0; pq.push(make_pair(0, 0)); // w - v while (pq.size()) { ll w; int v; tie(w, v) = pq.top(); pq.pop(); if (w > dis[v]) continue; for (auto& it : G[v]) { int new_w, nv; tie(nv, new_w) = it; new_w += w; if (dis[nv] > new_w) { pq.push(make_pair(new_w, nv)); dis[nv] = new_w; } } } for (int i = 0; i < n; ++i) cout << dis[i] << '\n'; // 实际上只需要 dis[2020] 即可! return 0; } ```