#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; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:1106 |
简单的a+b (C语言代码)浏览:650 |
C语言程序设计教程(第三版)课后习题6.6 (C语言代码)浏览:356 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:710 |
Minesweeper (C语言描述,蓝桥杯)浏览:1165 |
C二级辅导-分段函数 (C语言代码)浏览:652 |
The 3n + 1 problem (C语言代码)浏览:540 |
Quadratic Equation (C语言代码)浏览:1027 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:782 |
半数集问题 (C语言代码)浏览:957 |