小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图
中的最短路径。
小蓝的图由
2021
个结点组成，依次编号
1
至
2021
。
对于两个不同的结点
a
,
b
，如果
a
和
b
的差的绝对值大于
21
，则两个结点
之间没有边相连；如果
a
和
b
的差的绝对值小于等于
21
，则两个点之间有一条
长度为
a
和
b
的最小公倍数的无向边相连。
例如：结点
1
和结点
23
之间没有边相连；结点
3
和结点
24
之间有一条无
向边，长度为
24
；结点
15
和结点
25
之间有一条无向边，长度为
75
。
请计算，结点
1
和结点
2021
之间的最短路径长度是多少
思路：最短路模板（稀疏图）套上，按题意处理储存路径就行了。
附赠最短路模板： disk求最短路_Demo.o的博客-CSDN博客
#include<iostream>//稀疏图
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N=150010;
int n=2021;
int e[N],ne[N],h[N],w[N],idx;
bool st[N];
int dist[N];
typedef pair<int,int> pii;void add(int a,int b,int c){e[idx]=b;ne[idx]=h[a];h[a]=idx;w[idx]=c;idx++;
}
int gcd(int a,int b){if(a<b)swap(a,b);if(b==0)return a;else{return gcd(b,a%b);}
}
int dikj(){memset(dist,0x3f,sizeof dist);dist[1]=0;priority_queue<pii,vector<pii>,greater<pii> > heap;heap.push({0,1});while(heap.size()){pii t=heap.top();heap.pop();int d=t.first ,num=t.second ;if(st[num])continue;//判断状态st[num]=true;for(int i=h[num];i!=-1;i=ne[i]){//i=ne[i]int j=e[i];if(dist[j]>d+w[i]){//+的是w[i]dist[j]=d+w[i];heap.push({dist[j],j});}}}if(dist[n]==0x3f3f3f3f)return -1;else return dist[n];
}
int main(){memset(h,-1,sizeof h);for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){if(abs(i-j)<=21){int c=gcd(i,j);int p=i/c*j;add(i,j,p);}}}printf("%d",dikj());return 0;
}