蓝桥杯第十二届 试题E 路径

记录蓝桥杯第十二届最后一道填空题，其实还蛮简单的 用了Dijkstra算法求最短路径 题在里面 https://blog.csdn.net/qq_44577309/article/details/115834519

#include<bits/stdc++.h>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
const int N =1e9;
int n;
struct cmp {
	bool operator()(const int&a,const int&b) const {
		return a>b;
	}
};
//int month[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31};
int gcd(int a,int b){
	return a%b==0? b:gcd(b,a%b);
}
int f(int a,int b){
	return a*b/gcd(a,b);
} 
int a[2025][2025];
int dis[2025];
bool s[2025];
int mini = N;
int main() {
	//fill(dis, dis + 2050, inf);
	memset(s,0,sizeof(s));
	//fill(dis, dis + 2025, N);
	fill(a[0], a[0] + 2025 * 2025, N);
	for(int i =1;i<=2021;i++){
		for (int j = 1; j <= 21;j++)    //21?????
        {
            int k = i + j;  //i???,k???
            if(k>2021)
                break;
            a[i][k] = a[k][i] = f(i, k);
        }   
	}
//	for(int i =1;i<=20;i++){
//		for(int j =1;j<=20;j++){
//			cout<<a[i][j]<<" ";
//		}
//		//if(i%5==0)
//		cout<<"\n";
//	}
	for(int i = 2;i<=2021;i++){
		//s[i]=false;
		if(a[1][i]!=N) dis[i]=a[1][i];
		else dis[i]=N;
	}
	dis[1]=0;
	s[1]=1;
	for(int i =1;i<=2021;i++){
		int k,mini=N;
		for(int j =1;j<=2021;j++){
			if(!s[j]&&dis[j]<mini){
				k = j;
				mini=dis[j];
			}
		}
		s[k]=1;
		for(int w = 1;w<=2021;w++){
			if(!s[w]&&dis[w]>dis[k]+a[k][w]){
				dis[w]=dis[k]+a[k][w];
			}
		}	
	}
//	for(int i =1;i<=2021;i++){
//		cout<<dis[i]<<" ";
//		if(i%5==0)
//		cout<<"\n";
//	}
	cout<<dis[2021];
	
	return 0;
}

Answer:10266837