首页 > 代码库 > Hdu2544 最短路径 四种方法
Hdu2544 最短路径 四种方法
Problem Description
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
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
最短路 (Bellman-Ford、Dijkstra and Floyd用三种方法写)
Bellman-Ford 求含负权图的单元最短路径(效率低)
//现在还有点不太懂bellman-ford 两重循环，第一层是 点的个数，第二层是边的个数的二倍。Map数组不用初始化
SPFA 用队列写，效率高 (平均入队次数不超过两次)有！
ps: SPFA是bellman-ford的优化，队列写（每个点平均入队次数不超过两次）。为了避免最坏的情况出现，一般用dijkstra，floyd基本不用
1.Floyd：
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;#define mx 1<<29int map[105][105];int n,m,a,b,c;void floyd(){ int i,j,k; for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) if(map[i][j]>map[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j]; printf("%d\n",map[1][n]);}int main(){ int i,j; while(scanf("%d%d",&n,&m)==2 && (m+n)) { for(i=1; i<=n; i++) for(j=1; j<=n; j++) map[i][j]=mx; while(m--) { scanf("%d%d%d",&a,&b,&c); map[a][b]=c; map[b][a]=c; } floyd(); } return 0;}
2.dijkstra
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;#define INF 0xfffffffint map[105][105];int v[105],d[105];int n,m,a,b,c;void dijkstra(){ memset(v,0,sizeof(v)); int i,j,k,p,min; for(i=1;i<=n;i++) d[i]=map[1][i]; v[1]=1; for(i=1;i<=n;i++){ min=INF; for(j=1;j<=n;j++) if(!v[j] && d[j]<min) min=d[j],p=j; v[p]=1; for(j=1;j<=n;j++){ if(!v[j] && d[j]>min+map[p][j]) d[j]=min+map[p][j]; } } printf("%d\n",d[n]);}int main(){ while(scanf("%d%d",&n,&m)==2 && (m+n)){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) map[i][j]=INF; while(m--){ scanf("%d%d%d",&a,&b,&c); map[a][b]=map[b][a]=c; } dijkstra(); } return 0;
3.SPFA:
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<queue>using namespace std;#define INF 1<<29int n,m,a,b,c;int map[105][105];int v[105],d[105];//有时候还要加前驱指针//记录每个节点进队的次数，如果>n,说明存在负环//SPFA无法处理带负环的问题void SPFA(){ memset(v,0,sizeof(v)); for(int i=1; i<=n; i++) d[i]=INF; queue<int>q; v[1]=1; d[1]=0; q.push(1); while(!q.empty()) { int x=q.front(); q.pop(); v[x]=0; for(int j=1; j<=n; j++) //最好是创建一个邻接表，提高效率 if(d[x]+map[x][j]<d[j]) { d[j]=d[x]+map[x][j]; if(!v[j]) { q.push(j); v[j]=1; } } } printf("%d\n",d[n]); return;}int main(){ while(scanf("%d%d",&n,&m)==2 && (m+n)) { for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) map[i][j]=INF; while(m--) { scanf("%d%d%d",&a,&b,&c); map[a][b]=map[b][a]=c; } SPFA(); } return 0;}
4.bellman_ford:
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;#define INF 1<<29struct Node{ int b,e,w;} v[5005];int n,m;int d[105];int bellman_ford(int b, int e){ for(int i=1; i<=n; i++) d[i]=INF; d[b]=0; for(int i=0; i<n-1; i++) for(int j=0; j<m*2; j++) d[v[j].e]=min(d[v[j].e], d[v[j].b]+v[j].w); return d[e];}int main(){ int a,b,c; while(~scanf("%d%d",&n,&m) && (m||n)) { for(int i=0; i<m; i++) { scanf("%d%d%d", &a,&b,&c); v[i].b=a; v[i].e=b; v[i].w=c; v[i+m].b=b; v[i+m].e=a; v[i+m].w=c; } printf("%d\n", bellman_ford(1,n)); } return 0;}
Hdu2544 最短路径 四种方法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。