记录蓝桥杯第十二届最后一道填空题,其实还蛮简单的 用了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