HDOJ 2544 最短路 (最短路 Dijkstra SPFA Floyd)

本文主要是介绍HDOJ 2544 最短路 (最短路 Dijkstra SPFA Floyd)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最短路

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 42602 Accepted Submission(s): 18666

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

Sample Output

3
2

注 - 此题为： HDOJ 2544 最短路 (最短路 Dijkstra)

说明：最短路 Dijkstra && SPFA &&Floyd（模板题）

已AC代码：(Dijkstra)

#include<cstdio>
#define INF 0xfffffff
#define min(x,y) (x<y?x:y)
int n,m;
int map[200][200],vis[200],d[200];void Dijkstra(int s) // 模板 
{int i,j;for(i=1;i<=n;++i){vis[i]=0;d[i]=INF;}d[s]=0;while(1){int j=-1;for(i=1;i<=n;++i){if(!vis[i]&&(j==-1||d[i]<d[j]))j=i;}if(j==-1) //全部遍历 break;vis[j]=1;for(i=1;i<=n;++i){d[i]=min(d[i],d[j]+map[j][i]);}}
}int main()
{int i,j,a,b,c;while(scanf("%d%d",&n,&m),n,m){for(i=1;i<=n;++i) //初始化 for(j=1;j<=n;++j)map[i][j]=INF;for(i=1;i<=m;++i){scanf("%d%d%d",&a,&b,&c);map[a][b]=c;map[b][a]=c;}Dijkstra(1);  //起点 为 1  终点为 n printf("%d\n",d[n]);}return 0;
}

已AC代码：（SPFA）

#include <cstdio>
#include <cstring>
#include <queue>
#define MAX 20000+10
#define INF 0x3f3f3f
using namespace std;struct Edge{int from,to,vel,next;
};
Edge edge[MAX];int head[MAX],cnt;
int N,M;
int dist[MAX],vis[MAX];void addedge(int u,int v,int w)
{edge[cnt].from=u;edge[cnt].to=v;edge[cnt].vel=w;edge[cnt].next=head[u];head[u]=cnt++;
}void SPFA(int st)  //模板 
{queue<int>Q;memset(dist,INF,sizeof(dist));memset(vis,0,sizeof(vis));Q.push(st);vis[st]=1;dist[st]=0;while(!Q.empty()){int u=Q.front();Q.pop();vis[u]=0;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(dist[v]>dist[u]+edge[i].vel){dist[v]=dist[u]+edge[i].vel;if(vis[v]==0){vis[v]=1;Q.push(v);}}}}printf("%d\n",dist[N]);
}int main()
{int i,j,a,b,c;while(scanf("%d%d",&N,&M),N,M){cnt=0;memset(head,-1,sizeof(head));while(M--){scanf("%d%d%d",&a,&b,&c);addedge(a,b,c);addedge(b,a,c);}SPFA(1);}return 0;
}

已AC代码：(Floyd)

#include<cstdio>
#include<cstring>
#define INF 0x3f3f3f
#define min(x,y) (x<y?x:y)int N,M;
int dist[125][125];void Floyd()  // 模板 
{int i,j,k;for(k=1;k<=N;++k)for(i=1;i<=N;++i)for(j=1;j<=N;++j)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}int main()
{int i,a,b,c;while(scanf("%d%d",&N,&M),N,M){memset(dist,INF,sizeof(dist));for(i=0;i<=N;++i)    // 初始化 dist[i][i]=0;for(i=0;i<M;++i){scanf("%d%d%d",&a,&b,&c);if(c<dist[a][b])  // 去重，取小 dist[a][b]=dist[b][a]=c;}Floyd();int d=dist[1][N];  // 起点为 1  ，终点为 N printf("%d\n",d);}return 0;
}

这篇关于HDOJ 2544 最短路 (最短路 Dijkstra SPFA Floyd)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！