第十二届蓝桥杯 填空 路径 Dijkstra算法

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll maxn = 2021 + 5;
const ll inf = 1e9;
vector<pair<int,ll>> a[maxn];
ll dist[maxn] , bk[maxn];
int main()
{
          
   
    ll n=2021;
    for(int i=1;i<=n;i++){
          
   
        for(int j=i+1;j<=n;j++){
          
   
            if(abs(i-j)<=21){
          
   
                a[i].push_back(make_pair(j,i/__gcd(i,j)*j));
                a[j].push_back(make_pair(i,i/__gcd(i,j)*j));
            }
        }
    }
    for (int i = 1 ; i <= n ; i++)
        dist[i] = inf;
    dist[1]=0;
  
    for (int i = 1 ; i <= n ; i++){
          
   
        ll mi = inf;
        ll x;
        
        for (int j = 1 ; j <= n ; j++){
          
   
            if (bk[j] == 1) continue;
            if (mi > dist[j]){
          
   
                mi = dist[j];
                x = j;
            }
        }
        bk[x] = 1;
        for (auto g : a[x]){
          
   
            int v = g.first , w = g.second;
            dist[v] = min(dist[v] , dist[x] + w);
        }
    }
    cout<<dist[n];
    return 0;
}