HDU 2066 一个人的旅行(SPFA +Floyd-Warshall算法)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了HDU 2066 一个人的旅行(SPFA +Floyd-Warshall算法),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3577字,纯文字阅读大概需要6分钟。
内容图文
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2066
一个人的旅行
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 24385 Accepted Submission(s): 8460
接着有T行,每行有三个整数a,b,time,表示a,b城市之间的车程是time小时;(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数,表示和草儿家相连的城市;
接着的第T+2行有D个数,表示草儿想去地方。
6 2 3 1 3 5 1 4 7 2 8 12 3 8 4 4 9 12 9 10 2 1 2 8 9 10
9
【题目大意】
给你一些通路,告诉你通过这些通路所需的时间。
然后给你可能的一些起始位置,, 可能的一些终点。
求出主人公去任意一个终点的最短时间。 去哪个终点都行,前提是用时最短。
多起点的最短路算法。
思路一,SPFA, 将起点都推入队列。求出各个终点的最短时间。然后再找到最短的;
【SPFA】
//SPFA shortest path faster algorithm #include <cstdio> #include <vector> #include <algorithm> #include <queue> #define INF 0xfffffff const int maxn = 1010; using namespace std; struct node{ int v,len; node(int v=0,int len=0):v(v),len(len){} }; int st[1010]; int goal[1010]; vector<node>G[maxn]; int minDist[maxn]; int inqueue[maxn]; int n,m; int T,S,D; void init(){ for(int i=0;i<maxn;i++){ minDist[i]=INF; inqueue[i]=0; G[i].clear(); } } int Dijkstra(){ <pre name="code" class="cpp"> queue<int >Q; for(int i=0;i<S;i++){ //将所有的起点 都推入队列 inqueue[st[i]]=true; minDist[st[i]]=0; Q.push(st[i]); } while(!Q.empty()){ int vex = Q.front(); Q.pop(); inqueue[vex]=0; for(int i=0;i<G[vex].size();i++){ int v = G[vex][i].v; if(G[vex][i].len+minDist[vex]<minDist[v]){ //松弛操作,找到最短边 minDist[v]=G[vex][i].len+minDist[vex]; if(!inqueue[v]) { inqueue[v]=1; Q.push(v); } } } } int Min = INF; for(int i=0;i<D;i++){ //在终点找到用时最小的终点 Min = min(minDist[goal[i]],Min); } printf("%d\n",Min); } int main(){ while(scanf("%d%d%d",&T,&S,&D)!=EOF){ init(); int a,b,len; for(int i=0;i<T;i++){ scanf("%d%d%d",&a,&b,&len); G[a].push_back(node(b,len)); G[b].push_back(node(a,len)); } for(int i=0;i<S;i++){ scanf("%d",&st[i]); } for(int i=0;i<D;i++){ scanf("%d",&goal[i]); } Dijkstra(); } return 0; }
【Floyd-Warshall算法】
效率是O(n^3) 用到了DP的思想,还没太搞明白,不过会用了,以后学DP后在回来看吧
#include <cstdio> #include <vector> #include <queue> #define INF 0xfffff const int maxn = 1010; using namespace std; int map[maxn][maxn]; int st[maxn]; int goal[maxn]; void init(){ for(int i=1;i<maxn;i++){ for(int j=1;j<maxn;j++){ if(i==j) map[i][j]=0; else map[i][j]=INF; } } } int main(){ int T,S,D; while(scanf("%d%d%d",&T,&S,&D)!=EOF){ init(); int a,b,len; int Min=INF,Max=-1; for(int i=0;i<T;i++){ scanf("%d%d%d",&a,&b,&len); if(a>Max) Max = a; if(b>Max) Max = b; if(b<Min) Min = b; if(a<Min) Min =a; if(len<map[a][b]) { map[a][b]=map[b][a]=len; } } for(int k=Min;k<=Max;k++){ for(int i=Min;i<=Max;i++){ if(map[i][k]!=INF) //没有这句优化就超时了 for(int j=Min;j<=Max;j++){ if(map[i][j]>map[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j]; } } } for(int i=0;i<S;i++) scanf("%d",&st[i]); for(int i=0;i<D;i++) scanf("%d",&goal[i]); int ans=INF; for(int i=0;i<S;i++){ for(int j=0;j<D;j++){ if(map[st[i]][goal[j]]<ans) ans=map[st[i]][goal[j]]; } } printf("%d\n",ans); } return 0; }
版权声明:本文为博主原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/chaiwenjun000/article/details/47450655
内容总结
以上是互联网集市为您收集整理的HDU 2066 一个人的旅行(SPFA +Floyd-Warshall算法)全部内容,希望文章能够帮你解决HDU 2066 一个人的旅行(SPFA +Floyd-Warshall算法)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。