第十二届蓝桥杯B组E路径

//迪杰斯特拉求最短路
#include<bits/stdc++.h>
using namespace std;
int a[2022][2022];
int gcd(int x,int y){
	if(y==0){
		return x;
	}else{
		return gcd(y,x%y);
	}
}
int main(){
	int n=2021;
	int dis[2022],book[2022],i,j,inf=0x3f3f3f3f,min,u,v;
	for(i=1;i<=2021;i++){
		for(j=1;j<=2021;j++){
			if (i==j){
				a[i][j]=0;
			}else{a[i][j]=inf; }
		}
	}
	for(i=1;i<=2021;i++){
		for(j=1;j<=2021;j++){
			if(abs(i-j)<=21&&i!=j)
			a[i][j]=i*j/gcd(i,j);
		}
	}
	for(i=1;i<=2021;i++)
	dis[i]=a[1][i];
	for(i=1;i<=2021;i++)
	book[i]=0;
	book[1]=1;
	for(i=1;i<=2020;i++){
		min=inf;
		for(j=1;j<=2021;j++){
			if(book[j]==0&&dis[j]<min){
				min=dis[j];
				u=j;
			}
		} 
		book[u]=1;
		for(v=1;v<=2021;v++){
			if(a[u][v]<inf){
			if(dis[v]>dis[u]+a[u][v]){
				dis[v]=dis[u]+a[u][v];
			}
		}
	}
}
	printf("%d",dis[2021]);
}
//答案：10266837

最后

以上就是正直龙猫为你收集整理的第十二届蓝桥杯B组E路径的全部内容，希望文章能够帮你解决第十二届蓝桥杯B组E路径所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。