Description

经过锦囊相助,海东集团终于度过了危机,从此,HDU的发展就一直顺风顺水,到了2050年,集团已经相当规模了,据说进入了钱江肉丝经济开发区500强。这时候,XHD夫妇也退居了二线,并在风景秀美的诸暨市�浦镇陶姚村买了个房子,开始安度晚年了。
这样住了一段时间,徐总对当地的交通还是不太了解。有时很郁闷,想去一个地方又不知道应该乘什么公交车,在什么地方转车,在什么地方下车(其实徐总自己有车,却一定要与民同乐,这就是徐总的性格)。

徐总经常会问蹩脚的英文问路:“Can you help me?”。看着他那迷茫而又无助的眼神,热心的你能帮帮他吗?

请帮助他用最短的时间到达目的地(假设每一路公交车都只在起点站和终点站停,而且随时都会开)。
 

Input

输入数据有多组,每组的第一行是公交车的总数N(0<=N<=10000);

第二行有徐总的所在地start,他的目的地end;

接着有n行,每行有站名s,站名e,以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。

note:一组数据中地名数不会超过150个。

如果N==-1,表示输入结束。
 

Output

如果徐总能到达目的地,输出最短的时间;否则,输出“-1”。
 

Sample Input

6
xiasha westlake
xiasha station 60
xiasha ShoppingCenterofHangZhou 30
station westlake 20
ShoppingCenterofHangZhou supermarket 10
xiasha supermarket 50
supermarket westlake 10
-1
 

Sample Output

50

Hint:
The best route is:
xiasha->ShoppingCenterofHangZhou->supermarket->westlake

虽然偶尔会迷路,但是因为有了你的帮助
**和**从此还是过上了幸福的生活。

��全剧终��

 
 
这个题目是个裸的单源最短路,不过需要处理地名和数字的转换,这里用了map(不过string速度真的很慢)。
此处采用了spfa,用了优先队列进行优化。
 
代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
#define LL long long using namespace std; typedef pair<int, int> pii;
const int maxN = ; //链式前向星
struct Edge
{
int to, next;
int val;
}edge[maxN*]; int head[maxN], cnt; void addEdge(int u, int v, int val)
{
edge[cnt].to = v;
edge[cnt].val = val;
edge[cnt].next = head[u];
head[u] = cnt;
cnt++;
} void initEdge()
{
memset(head, -, sizeof(head));
cnt = ;
} int n;
map<string, int> Hash;
string from, to;
int fromId, toId;
int dis[maxN]; void input()
{
initEdge();
Hash.clear();
memset(dis, -, sizeof(dis));
int num = ;
cin >> from >> to;
Hash[from] = num++;
if (!Hash[to])
Hash[to] = num++;
string u, v;
int cost;
for (int i = ; i < n; ++i)
{
cin >> u >> v >> cost;
if (!Hash[u])
Hash[u] = num++;
if (!Hash[v])
Hash[v] = num++;
addEdge(Hash[u], Hash[v], cost);
addEdge(Hash[v], Hash[u], cost);
}
fromId = Hash[from];
toId = Hash[to];
dis[fromId] = ;
} void SPFA()
{
pii k;
priority_queue <pii, vector<pii>, greater<pii> > q;
q.push(pii(dis[fromId], fromId));
int x;
while (!q.empty())
{
k = q.top();
q.pop();
x = k.second;
for (int i = head[x]; i != -; i = edge[i].next)
{
if (dis[edge[i].to] == - || dis[edge[i].to] > dis[x]+edge[i].val)
{
dis[edge[i].to] = dis[x]+edge[i].val;
q.push(pii(dis[edge[i].to], edge[i].to));
}
}
}
} int main()
{
//freopen("test.in", "r", stdin);
while (scanf("%d", &n) != EOF && n != -)
{
input();
SPFA();
printf("%d\n", dis[toId]);
}
return ;
}
05-08 08:07