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 = ;

 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 ;

 }

巴特西

HDU 2112 HDU Today 最短路

最新文章

热门文章