/* 3 3 1 2 2 2 3 1 1 3 4 */ //找到到达起点的最短路 #include<iostream> #include<cstring> using namespace std; const int N=500; int g[N][N],dist[N],n,m; //g存图 dist存各点到起点最短距离 bool st[N]; //标记已经走过 int dijkstra() { memset(dist,0x3f,sizeof(dist)); //初始化所有点到起点的距离为正无穷 dist[1]=0; //起点到起点的距离为0 for(int i=1;i<=n;i++) //迭代n次 { int t=-1; //在还未确定的最短路中 找到距离最小的点 for(int j=1;j<=n;j++) if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; st[t]=true; //标记 for(int j=1;j<=n;j++) { dist[j] = min(dist[j], dist[t] + g[t][j]); //用 找到的最短的点 更新其他点 } } if(dist[n]==0x3f3f3f) return -1; else return dist[n]; } int main(void) { memset(g,0x3f,sizeof(g)); //初始化所有点间的距离为正无穷 cin>>n>>m; while(m--) { int a,b,c; cin>>a>>b>>c; g[a][b]=min(g[a][b],c); //要找最小的 } int t=dijkstra(); cout<<t<<endl; return 0; }
0.0分
1 人评分
2005年春浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:591 |
最小公倍数 (C语言代码)浏览:1029 |
矩阵加法 (C语言代码)浏览:1723 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:1175 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:345 |
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:617 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:544 |
母牛的故事 (C语言代码)浏览:570 |
筛排处理 (C语言代码)浏览:789 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:580 |