迪杰特斯拉算法

#include
#define endl "n"
using namespace std;
typedef long long ll;
const int maxN=2e4+10;
int weight[maxN][maxN];
const int oo=0x3f3f3f3f;
int cmp(int i,int j){
    if(i%j==0){return j;}
    else {return cmp(j,i%j);}
}
bool vis[maxN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(int i=1;i<=2021;i++){
        for(int j=1;j<=2021;j++){
            weight[i][j]=oo;
        }
    }
    for(int i=1;i<=2021;i++){
        for(int j=1;j<=2021;j++){
            if(abs(i-j)<=21){
                weight[i][j]=i*j/cmp(max(i,j),min(i,j));
            }
        }
    }
    weight[1][1]=0;
    vis[1]=true;
    int viscnt=1;
    while(viscnt<2021){
        int minW=oo;
        int minpos=-1;
        for(int v=1;v<=2021;v++){
            if(!vis[v]&&weight[1][v]weight[1][minpos]+weight[minpos][v])){
                    weight[1][v]=weight[1][minpos]+weight[minpos][v];
                }
            }
        }
        else {break;}
    }
    cout<