一个点最少有21条边 稠密图 邻接矩阵存
法一:dijkstra的朴素做法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 1e6+10;
int g[2050][2050];
int dist[N];
bool st[N];
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
void dijkstra(){// 求1号点到n号点的最短路距离
    memset(dist,0x3f,sizeof dist);//求最短路 先初始化为正无穷
    dist[1]=0;//到自己距离为0
    for (int i=1;i<=2021;i++){//枚举每一个点
        int t=-1;//t存储每一轮离起点最近的点的编号
        for (int j=1;j<=2021;j++){//找最近的点
//最近的点必须满足 是所有没走过的点里离起点最近的
            if (!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
        }
        for (int j=1;j<=2021;j++){//开始更新与t联通的点
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
        st[t]=1;//标记t已经走过了
    }
}
int main(){
    memset(g,0x3f,sizeof g);
    for (int i=1;i<=2021;i++){
        for (int j=1;j<=2021;j++){
            if (abs(i-j)<=21) {
                g[i][j]=i*j/gcd(i,j);
            }
        }
    }
    dijkstra();
    cout<<dist[2021];//10266837
    return 0;
}

法二:堆优化的dijkstra

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 1e6+10;
int idx,e[N],ne[N],w[N],h[N];
int dist[N];
bool st[N];
void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
void dijkstra(){// 求1号点到n号点的最短路距离
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue <pii,vector<pii>,greater<pii>> heap;
    heap.push({0,1});
    while (heap.size()){
        auto t=heap.top();
        heap.pop();
        int ver=t.y,len=t.x;
        if (st[ver]) continue;
        st[ver]=1;
        for (int i=h[ver];~i;i=ne[i]){
            int j=e[i];
            if (dist[j]>dist[ver]+w[i]){
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});
            }
        }
    }
}
int main(){
    memset(h, -1, sizeof h);
    for (int i=1;i<=2021;i++){
        for (int j=1;j<=2021;j++){
            if (abs(i-j)<=21) {
                add(i,j,i*j/gcd(i,j));
            }
        }
    }
    dijkstra();
    cout<<dist[2021];//10266837
    return 0;
}