hdu2544(裸最短路dijkstra)

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

最短路

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 34140 Accepted Submission(s): 14820

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

第一份代码，朴素dijkstra算法:

//Cost Time  &&  Cost Memory  && Code Length

31MS

1292K

1371 B

<span style="color:#000000;">#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>using namespace std;#define inf 10000000
const int maxn = 12000;
const int Max = 150;
int a[Max][Max];
int dis[maxn];
bool vis[maxn];
int m,n;void dij(int src)
{memset(vis,0,sizeof(vis));for(int i=1;i<=m;i++){dis[i] = a[src][i];}vis[src] = true;for(int i=1;i<m;i++){int temp = inf,k = src;for(int j=1;j<=m;j++){if(vis[j]) continue;if(temp > dis[j]){temp = dis[j];k = j;}}vis[k] = true;for(int j=1;j<=m;j++){if(vis[j]) continue;dis[j] = min(dis[j],dis[k]+a[k][j]);}}
}int main()
{int i,j,temp1,temp2,distance;//freopen("1","r",stdin);while(cin>>m>>n && (m || n)){for(i=0;i<Max;i++){for(j=0;j<Max;j++){a[i][j] = inf;}}memset(dis,0,sizeof(dis));for(i=1;i<=n;i++){cin>>temp1>>temp2>>distance;a[temp1][temp2] = distance;a[temp2][temp1] = distance;}dij(1);cout<<dis[m]<<endl;}return 0;
}</span>

第二份为用优先队列写的dijkstra代码：

//Cost Time  &&  Cost Memory  && Code Length

46MS

1388K

1237 B

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
const int Ni = 10000;
const int inf = 1<<27;
struct node
{int x,d;node() {}node(int a,int b) {x = a,d = b;}bool operator < (const node &a) const{if(d == a.d) return x < a.x;else return d > a.d;}
};
vector<node> eg[Ni];
int dis[Ni],n;
void Dijkstra(int s)
{int i;for(i=0;i<=n;i++) dis[i] = inf;dis[s] = 0;//用优先队列优化priority_queue<node> q;q.push(node(s,dis[s]));while(!q.empty()){node x = q.top();q.pop();for(i=0;i<eg[x.x].size();i++){node y = eg[x.x][i];if(dis[y.x] > x.d + y.d){dis[y.x] = x.d + y.d;q.push(node(y.x,dis[y.x]));}}}
}
int main()
{int a,b,d,m;while(cin>>n>>m && n+m){for(int i=0;i<=n;i++) eg[i].clear();while(m--){cin>>a>>b>>d;eg[a].push_back(node(b,d));eg[b].push_back(node(a,d));}Dijkstra(1);cout<<dis[n]<<endl;}return 0;
}

第三份为优先队列实现dijkstra + 读入外挂(可以看出读入外挂的优势)

//Cost Time  &&  Cost Memory  && Code Length<table class="table_text " align="center" border="0" cellspacing="2" width="100%"><tbody><tr align="center"><td>15MS</td><td>1388K</td><td><a target=_blank href="http://acm.hdu.edu.cn/viewcode.php?rid=12428092" target="_blank">1507 B</a></td></tr></tbody></table>#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
const int Ni = 10000;
const int inf = 1<<27;
struct node
{int x,d;node() {}node(int a,int b) {x = a,d = b;}bool operator < (const node &a) const{if(d == a.d) return x < a.x;else return d > a.d;}
};
vector<node> eg[Ni];
int dis[Ni],n;void Read(int &a){char ch;a = 0;ch = getchar();while( !(ch >= '0' && ch <= '9') ) ch = getchar();while((ch >= '0' && ch <= '9') ){a = a * 10 + ch - '0';ch = getchar();}
}
void Dijkstra(int s)
{int i;for(i=0;i<=n;i++) dis[i] = inf;dis[s] = 0;//用优先队列优化priority_queue<node> q;q.push(node(s,dis[s]));while(!q.empty()){node x = q.top();q.pop();for(i=0;i<eg[x.x].size();i++){node y = eg[x.x][i];if(dis[y.x] > x.d + y.d){dis[y.x] = x.d + y.d;q.push(node(y.x,dis[y.x]));}}}
}
int main()
{int a,b,d,m;while(cin>>n>>m && n+m){for(int i=0;i<=n;i++) eg[i].clear();while(m--){Read(a);Read(b);Read(d);eg[a].push_back(node(b,d));eg[b].push_back(node(a,d));}Dijkstra(1);cout<<dis[n]<<endl;}return 0;
}

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