1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include<iostream>#include<algorithm>#include<cstring> using namespace std;const int N=1e1+10;int n,m;int dis[N],g[N][N]; //dis存每个点到起点的最短距离 g存a到b的距离 bool st[N]; //判断该点是否已经是最短距离 int find(){ memset(dis,0x3f,sizeof dis); dis[1]=0; //初始化所有点距离都为无穷 ，起点距离为0 for(int i=0;i<n;i++) //n个点循环n次 { int t=-1; for(int j=1;j<=n;j++) //每次找出还未确定点中最短的点 { if(!st[j]&&(t==-1||dis[t]>dis[j])) t=j; } for(int j=1;j<=n;j++) //更新所有点的距离 dis[j]=min(dis[j],dis[t]+g[t][j]); st[t]=true; } if(dis[n]==0x3f3f3f3f)return -1; return dis[n]; } int main(void){ cin>>n>>m; memset(g,0x3f,sizeof g); while(m--) { int a,b,x; cin>>a>>b>>x; g[a][b]=min(g[a][b],x); //保证a到b为最短，考虑a到b有多条边的情况 } int t=find(); cout<<t<<endl; return 0;} |
9.9 分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复