题目描述：
Problem 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
解题报告：
感觉这题好坑，一开始没看到时间限制是5000ms，所以一直想用迪杰斯特拉过，但是这题有一个到底能否到达的问题，所以用弗洛伊德比较好，要注意的问题是要注意判断起点和终点相同的情况，直接输出0就可以 了，还有就是这题我一开始用暴力判断输入的地名前面有没有出现过，时间较短，但是后面用STL里面的map容器来判断时间反而变长了，一直不解，希望哪位知道的看到了可以告诉我。两种代码都附上吧。
用了STL的代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<string>
using namespace std;
const int MAX = 0xffffff,SIZE = ;
int Map[SIZE][SIZE];
char str1[][],str2[][];
int str3[];
int n,f;
map<string,int> map1;
int judge(char *p) {
string s1 = p;
pair<map<string,int>::iterator,bool> iter;
iter = map1.insert(pair<string,int> (s1,++f));
if(iter.second)
return f;
else {
f--;
return map1[s1];
}
}
int main() {
char sta[],end[];
int s,e;
while(scanf("%d",&n)&&n!=-) {
map1.clear();
scanf("%s%s",sta,end);
f = ;
for(int i = ;i<=n;++i)
scanf("%s%s%d",str1[i],str2[i],&str3[i]);
if(!strcmp(sta,end)) {
printf("0\n");
continue;
}
for(int i = ;i<SIZE;++i) {
Map[i][i] = ;
for(int j = ;j<SIZE;++j)
Map[i][j] = MAX;
} for(int i = ;i<=n;++i) {
int x = judge(str1[i]);
int y = judge(str2[i]);
Map[x][y] = Map[y][x] = str3[i];
}
s = judge(sta);
e = judge(end);
for(int i = ;i<=f;++i)
for(int j = ;j<=f;++j)
for(int k = ;k<=f;++k)
Map[j][k] = std::min(Map[j][i]+Map[i][k],Map[j][k]);
if(Map[s][e]==MAX)
printf("-1\n");
else printf("%d\n",Map[s][e]);
}
return ;
}
没用STL的代码：
#include<cstdio>
#include<cstring>
#include<iostream>
const int MAX = 0xffffff,SIZE = ;
int map[SIZE][SIZE];
char str1[][],str2[][],str[][];
int str3[];
int n,f;
int judge(char *p) {
for(int i = ;i<=f;++i)
if(!strcmp(str[i],p))
return i;
strcpy(str[++f],p);
return f;
}
int main() {
char s1[],s2[],sta[],end[];
int s,e;
while(scanf("%d",&n)&&n!=-) {
scanf("%s%s",sta,end);
f = ;
for(int i = ;i<=n;++i)
scanf("%s%s%d",str1[i],str2[i],&str3[i]);
if(!strcmp(sta,end)) {
printf("0\n");
continue;
}
for(int i = ;i<SIZE;++i) {
map[i][i] = ;
for(int j = ;j<SIZE;++j)
map[i][j] = MAX;
}
for(int i = ;i<=n;++i) {
int x = judge(str1[i]);
int y = judge(str2[i]);
map[x][y] = map[y][x] = str3[i];
}
s = judge(sta);
e = judge(end);
for(int i = ;i<=f;++i)
for(int j = ;j<=f;++j)
for(int k = ;k<=f;++k)
map[j][k] = std::min(map[j][i]+map[i][k],map[j][k]);
if(map[s][e]==MAX)
printf("-1\n");
else printf("%d\n",map[s][e]);
}
return ;
}