hdu2680 Choose the best route 最短路(Dijkstra算法)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了hdu2680 Choose the best route 最短路(Dijkstra算法),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4027字,纯文字阅读大概需要6分钟。
内容图文
Choose the best route
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Each case begins with three integers n, m and s,(n<1000,m<20000,1=<s<=n) n stands for the number of bus stations in this city and m stands for the number of directed ways between bus stations .(Maybe there are several ways between two bus stations .) s stands for the bus station that near Kiki’s friend’s home.
Then follow m lines ,each line contains three integers p , q , t (0<t<=1000). means from station p to station q there is a way and it will costs t minutes .
Then a line with an integer w(0<w<n), means the number of stations Kiki can take at the beginning. Then follows w integers stands for these stations.
5 8 5 1 2 2 1 5 3 1 3 4 2 4 7 2 5 6 2 3 5 3 5 1 4 5 1 2 2 3 4 3 4 1 2 3 1 3 4 2 3 2 1 1
1 -1
#include<stdio.h> #include<string.h> #define INF 1<<26 const int N = 1e3 + 10; int w[N][N], d[N]; void Dijkstra(int n, int u) { int vis[N], i; memset(vis, 0, sizeof(vis)); for(i = 0; i <= n; i++) d[i] = INF; d[u] = 0; for(i = 0; i <= n; i++) { int x = u, temp = INF; for(int y = 0; y <= n; y++) if(!vis[y] && d[y] < temp) temp = d[x = y]; if(temp == INF) break; vis[x] = 1; for(int y = 0; y <= n; y++) if(d[y] > d[x] + w[x][y]) d[y] = d[x]+ w[x][y]; } } int main() { int n, m, des, i, j; while(~scanf("%d%d%d",&n, &m, &des)) { for(i = 0; i <= n; i++) for(j = 0; j <= n; j++) { if(i == j) w[i][j] = 0; else w[i][j] = INF; } int a, b, c; for(i = 0; i < m; i++) { scanf("%d%d%d",&a, &b, &c); if(c < w[a][b]) w[a][b] = c; //两个车站之间如果有多条路,选择最短的一条 } int num, p; scanf("%d",&num); for(i = 0; i < num; i++) { scanf("%d",&p); w[0][p] = 0; //自己加一个起点,把图更新 } Dijkstra(n, 0); if(d[des] < INF) printf("%d\n",d[des]); else printf("-1\n"); } return 0; }
思路二代码:
#include<stdio.h> #include<string.h> #define INF 1<<26 const int N = 1e3 + 10; int w[N][N], d[N]; void Dijkstra(int n, int u) { int vis[N], i; memset(vis, 0, sizeof(vis)); for(i = 1; i <= n; i++) d[i] = INF; d[u] = 0; for(i = 1; i <= n; i++) { int x = u, temp = INF; for(int y = 1; y <= n; y++) if(!vis[y] && d[y] < temp) temp = d[x = y]; if(temp == INF) break; vis[x] = 1; for(int y = 1; y <= n; y++) if(d[y] > d[x] + w[x][y]) d[y] = d[x] + w[x][y]; } } int main() { int n, m, des, i, j; while(~scanf("%d%d%d",&n, &m, &des)) { for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) { if(i == j) w[i][j] = 0; else w[i][j] = INF; } int a, b, c; for(i = 0; i < m; i++) { scanf("%d%d%d",&a, &b,&c); if(c < w[b][a]) w[b][a] = c; //路也反向 } Dijkstra(n, des); //终点作为起点 int num, Min_path = INF, p; scanf("%d",&num); for(i = 0; i < num; i++) { scanf("%d",&p); if(d[p] < Min_path) Min_path = d[p]; //记录最小值 } if(Min_path < INF) printf("%d\n",Min_path); else printf("-1\n"); } return 0; }
原文:http://blog.csdn.net/lyhvoyage/article/details/19190585
内容总结
以上是互联网集市为您收集整理的hdu2680 Choose the best route 最短路(Dijkstra算法)全部内容,希望文章能够帮你解决hdu2680 Choose the best route 最短路(Dijkstra算法)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。