文章

路径(2021省赛)

路径.png

dijkstra算法+最小公倍数

//路径 
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f3f3f;
long long int n=2021;
long long int a[6000][6000];
long long int dist[6000];
long long int flag[6000];
long long int cal(long long int x,long long int y){
    if(x==y) return 0;
    long long int r=1;
    long long int p=x;
    long long int q=y;
    while(r!=0){
        r=x%y;
        x=y;
        y=r;
    }
    return p*q/x;
}
void init(){
    long long int i,j;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(i!=j) a[i][j]=inf;
            else a[i][j]=0;
        }
    }
    for(i=1;i<=n;i++){
        for(j=i+1;j<=i+21&&j<=n;j++){
            a[i][j]=a[j][i]=cal(i,j);
        }
    }
    for(i=1;i<=n;i++){
        dist[i]=a[i][1];
    }
//  for(i=1;i<=n;i++){
//      cout<<dist[i]<<' ';
//  }cout<<endl;
    return ;
} 
void show(){
    long long int i,j;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
}
int findmin(){
    long long int minn=inf,i;
    long long int minloc=-1;
    long long int index=-1;
    for(i=1;i<=n;i++){
        if(flag[i]==0&&(index==-1||dist[i]<dist[index])){
            index=i;
        }
    }
    flag[index]=1;
    return index;
}
int dijkstra(){
    long long int i;
    while(1){
        long long int key=findmin();
        if(key==-1){
            break;
        }
        for(i=1;i<=n;i++){
            if(flag[i]==0&&dist[key]+a[key][i]<dist[i]){
                dist[i]=dist[key]+a[key][i];
            }
        }
    }
    return dist[n];
}
int main()
{
    init();
//  show();
    cout<<dijkstra()<<endl;
    return 0;
}

原题链接

https://www.lanqiao.cn/problems/1460/learning/

License:  CC BY 4.0