hdu-2544 最短路(最短路)
2018-08-21 05:28:28来源:博客园 阅读 ()
Input输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
Output对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间Sample Input
2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0
Sample Output
3 2
题解 最短路的模版题,我用的dijkstra,简单的说就是先找第一个点的所有的连它的边的最短的那条,把它加进去后,把连进去的点和原先的点看成同一个点,在找下一个离这个边最短的点,
#include<iostream> #include<algorithm> #include<cstring> #include<sstream> #include<cmath> #include<cstdlib> #include<queue> using namespace std; #define PI 3.14159265358979323846264338327950 const int x=110; const int INF=9999999; int cost[x][x],n,m; int d[x]; bool vis[x]; void dijkstra(int f ) { for(int i=1; i<=n; ++i) d[i] = INF; d[f] = 0; memset(vis, 0, sizeof(vis)); for(int i=1;i<=n;++i) { int u=-1; for(int j=1;j<=n;++j) if(!vis[j]) { if(u==-1 || d[j]<d[u]) u=j; } vis[u]=1; for(int j=1; j<=n; ++j) if(!vis[j]) { int tmp = d[u] + cost[u][j]; if(tmp<d[j]) d[j] = tmp; } } } int main(){ int a,b,c; while(~scanf("%d%d",&n,&m)&&n+m) { for(int i=1; i<=n; ++i) { cost[i][i]=INF; for(int j=i+1;j<=n;++j) cost[i][j]=cost[j][i]=INF; } for(int i=1;i<=m;i++) { scanf("%d %d %d",&a,&b,&c); cost[a][b]=cost[b][a]=c; } dijkstra(1); printf("%d\n",d[n]); } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:WINDOWS程序编程培训
下一篇:linux下条件变量使用笔记
- 设计一个多功能的MyTime类 代码参考 2020-03-29
- 设计MyTime类 代码参考 2020-03-29
- Run-Time Check Failure #0 - The value of ESP was not pro 2019-11-11
- Prime Time UVA - 10200(精度处理,素数判定) 2019-08-16
- bzoj1003: [ZJOI2006]物流运输(最短路+DP) 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash