HDU 2112 HDU Today 最短路

题目描述：

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 = 155;
int Map[SIZE][SIZE];
char str1[10005][40],str2[10005][40];
int str3[10005];
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[40],end[40];
   int s,e;
   while(scanf("%d",&n)&&n!=-1) {
       map1.clear();
       scanf("%s%s",sta,end);
       f = 0;
       for(int i = 1;i<=n;++i)
       scanf("%s%s%d",str1[i],str2[i],&str3[i]);
       if(!strcmp(sta,end)) {
           printf("0
");
           continue;
       }
       for(int i = 1;i<SIZE;++i) {
           Map[i][i] = 0;
           for(int j = 1;j<SIZE;++j)
           Map[i][j] = MAX;
       }
       
       for(int i = 1;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 = 1;i<=f;++i)
       for(int j = 1;j<=f;++j)
       for(int k = 1;k<=f;++k)
       Map[j][k] = std::min(Map[j][i]+Map[i][k],Map[j][k]);
       if(Map[s][e]==MAX)
       printf("-1
");
       else printf("%d
",Map[s][e]);
   }
   return 0;
}
           
       
View Code 

没用STL的代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 const int MAX = 0xffffff,SIZE = 155;
 5 int map[SIZE][SIZE];
 6 char str1[10005][40],str2[10005][40],str[10005][40];
 7 int str3[10005];
 8 int n,f;
 9 int judge(char *p) {
10     for(int i = 1;i<=f;++i)
11     if(!strcmp(str[i],p))
12     return i;
13     strcpy(str[++f],p);
14     return f;
15 }
16 int main() {
17     char s1[40],s2[40],sta[40],end[40];
18     int s,e;
19     while(scanf("%d",&n)&&n!=-1) {
20         scanf("%s%s",sta,end);
21         f = 0;
22         for(int i = 1;i<=n;++i)
23         scanf("%s%s%d",str1[i],str2[i],&str3[i]);
24         if(!strcmp(sta,end)) {
25             printf("0
");
26             continue;
27         }
28         for(int i = 1;i<SIZE;++i) {
29             map[i][i] = 0;
30             for(int j = 1;j<SIZE;++j)
31             map[i][j] = MAX;
32         }
33         for(int i = 1;i<=n;++i) {
34             int x = judge(str1[i]);
35             int y = judge(str2[i]);
36             map[x][y] = map[y][x] = str3[i];
37         }
38         s = judge(sta);
39         e = judge(end);
40         for(int i = 1;i<=f;++i)
41         for(int j = 1;j<=f;++j)
42         for(int k = 1;k<=f;++k)
43         map[j][k] = std::min(map[j][i]+map[i][k],map[j][k]);
44         if(map[s][e]==MAX)
45         printf("-1
");
46         else printf("%d
",map[s][e]);
47     }
48     return 0;
49 }

View Code

HDU 2112 HDU Today 最短路

相关推荐