2021第十二届蓝桥杯省赛B组C/C++

• 试题 E: 路径
• • 代码

试题 E: 路径

Ans=10266837
我哭了
最短路径的题考前刷了多少道，最后还是在考场翻车 还是太菜啊啊。。

首先是边权图的初始化，显然用邻接表保存权值要比邻接矩阵省点空间。
其次算权值需要算最小公倍数LCM，我考试直接用的加穷举的方法算LCM，太幼稚了，在N，M增大的时候，他们的LCM量级会显著增大（两被求数仅在万级时，其LCM就要达到亿级了），加穷举法的计算耗时会增加非常快，几乎没法儿用。
我考试的时候用加穷举，跑一遍几分钟（。。。我还抱怨赛题的问题 淦 太丢人了） 结果答案还跑不出来，气炸哦

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}    //辗转相除得GCDint lcm(int n,int m){return n/gcd(n,m)*m;}         //先除后乘 防止溢出

两个for循环初始化邻接表

for(int i=0;i<2021;i++){for(int j=i+1;j<=i+21&&j<2021;j++){

然后就是写Djikstra函数…
整个程序里的索引啥的把我折磨坏了…

代码

#include 
using namespace std;
typedef long long ll;
const int maxn = 2000000000;
int dis[2022];
int vi[2022];
typedef struct node{int index,co;node() :index(), co(){}node(int a,int b):index(a),co(b){}
}ta;
vector<ta> cost[2022];
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int lcm(int n,int m){return n/gcd(n,m)*m;}void djikstra(){dis[0]=0;for(int i=0;i<2021;i++){int u=-1,cmin=maxn;for(int j=0;j<2021;j++){if(vi[j]!=1&&dis[j]<cmin){u=j;cmin=dis[j];}}if(u==-1) return;vi[u]=1;int tar;for(int j=0;j<cost[u].size();j++){tar=cost[u][j].index;if(vi[tar]!=1&&(cost[u][j].co+cmin<dis[tar])){dis[tar]=cost[u][j].co+cmin;}}}
}
int main() {fill(dis,dis+2022,maxn);fill(vi,vi+2022,0);for(int i=0;i<2021;i++){for(int j=i+1;j<=i+21&&j<2021;j++){ta t;t=node(j,lcm(i+1,j+1));cost[i].push_back(t);}}djikstra();cout<<dis[2020];return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！