HDU 2112 HDU Today【最短路+map容器，spfa算法+Dijkstra算法】
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了HDU 2112 HDU Today【最短路+map容器，spfa算法+Dijkstra算法】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2385字，纯文字阅读大概需要4分钟。
内容图文
HDU Today
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 25102 Accepted Submission(s): 6067
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。
徐总经常会问蹩脚的英文问路：“Can you help me?”。看着他那迷茫而又无助的眼神，热心的你能帮帮他吗？
请帮助他用最短的时间到达目的地（假设每一路公交车都只在起点站和终点站停，而且随时都会开）。
第二行有徐总的所在地start，他的目的地end；
接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。
note：一组数据中地名数不会超过150个。
如果N==-1，表示输入结束。
6
xiasha westlake
xiasha station 60
xiasha ShoppingCenterofHangZhou 30
station westlake 20
ShoppingCenterofHangZhou supermarket 10
xiasha supermarket 50
supermarket westlake 10
-1
50
Hint:
The best route is:
xiasha->ShoppingCenterofHangZhou->supermarket->westlake
虽然偶尔会迷路，但是因为有了你的帮助
**和**从此还是过上了幸福的生活。
――全剧终――
原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=2112
此题我的Dijkstra算法代码老是RE，找不到错误。。。
spfa算法AC代码：
#include <iostream>
#include <cstdio>
#include <map>
#include <queue>
using namespace std;
const int INF=0x3f3f3f3f;
int a[155][155];
int dis[155];
bool vis[155];
int n,m;
void spfa()
{
for(int i=1; i<=n; i++)
{
dis[i]=INF;
vis[i]=false;
}
dis[1]=0;
vis[1]=true;
queue<int>q;
q.push(1);
while(!q.empty())
{
int p=q.front();
q.pop();
vis[p]=false;
for(int i=1; i<=n; i++)
{
if(dis[i]>dis[p]+a[p][i])
{
dis[i]=dis[p]+a[p][i];
if(!vis[i])
{
vis[i]=true;
q.push(i);
}
}
}
}
}
int main()
{
char s[35],e[35];
char ss[35],ee[35];
int d;
map<string,int>mapp;
while(scanf("%d",&m)!=EOF,m!=-1)
{
for(int i=0; i<155; i++)
{
for(int j=0; j<155; j++)
if(i==j) a[i][j]=0;
else a[i][j]=INF;
}
mapp.clear();
cin>>ss>>ee;
n=0;
mapp[ss]=++n;
if(mapp[ee]==0)
mapp[ee]=++n;
while(m--)
{
scanf("%s%s%d",&s,&e,&d);
if(mapp[s]==0) mapp[s]=++n;
if(mapp[e]==0) mapp[e]=++n;
if(a[mapp[s]][mapp[e]]>d)
a[mapp[s]][mapp[e]]=a[mapp[e]][mapp[s]]=d;
}
spfa();
if(dis[mapp[ee]]>=INF)
cout<<"-1"<<endl;
else
cout<<dis[mapp[ee]]<<endl;
}
return 0;
}
原文：http://blog.csdn.net/hurmishine/article/details/52059242
内容总结
以上是互联网集市为您收集整理的HDU 2112 HDU Today【最短路+map容器，spfa算法+Dijkstra算法】全部内容，希望文章能够帮你解决HDU 2112 HDU Today【最短路+map容器，spfa算法+Dijkstra算法】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。