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、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复