首页 > ACM题库 > HDU-杭电 > hdu 2112 HDU Today-Dijkstra-[解题报告]C++
2013
12-29

hdu 2112 HDU Today-Dijkstra-[解题报告]C++

HDU Today

问题描述 :

经过锦囊相助,海东集团终于度过了危机,从此,HDU的发展就一直顺风顺水,到了2050年,集团已经相当规模了,据说进入了钱江肉丝经济开发区500强。这时候,XHD夫妇也退居了二线,并在风景秀美的诸暨市�浦镇陶姚村买了个房子,开始安度晚年了。
这样住了一段时间,徐总对当地的交通还是不太了解。有时很郁闷,想去一个地方又不知道应该乘什么公交车,在什么地方转车,在什么地方下车(其实徐总自己有车,却一定要与民同乐,这就是徐总的性格)。
徐总经常会问蹩脚的英文问路:“Can you help me?”。看着他那迷茫而又无助的眼神,热心的你能帮帮他吗?
请帮助他用最短的时间到达目的地(假设每一路公交车都只在起点站和终点站停,而且随时都会开)。

输入:

输入数据有多组,每组的第一行是公交车的总数N(0<=N<=10000);
第二行有徐总的所在地start,他的目的地end;
接着有n行,每行有站名s,站名e,以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。
note:一组数据中地名数不会超过150个。
如果N==-1,表示输入结束。

输出:

输入数据有多组,每组的第一行是公交车的总数N(0<=N<=10000);
第二行有徐总的所在地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


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

��全剧终��

好悲剧的一题,wa了十四次啊!啊!啊!啊!啊!啊!

好吧,其实挺简单的一题,注意以下几点就可以了

第一,无向图

第二,看清题意,明白输入输出

第三,注意函数传递参数(14次的根本原因就是这里,有木有!!!)

直接上代码,map + Dijkstra

#include<map>
 #include<string>
 #include<iterator>
 #include<iostream>
 #include<algorithm>
 using namespace std;
 
 map<string, int> treeMap;
 map<string, int>::iterator mapIter1;
 map<string, int>::iterator mapIter2;
 const int inf = 1000000;
 const int Size = 160;
 
 bool vis[Size];
 int dist[Size];
 int cost[Size][Size];
 
 void Dijkstra(int v, int w, int n)
 {
     int i,j;
     int u;
     int min;
 
     for(i = 1; i <= n; i ++)
     {
         dist[i] = cost[v][i];
         vis[i] = false;
     }
 
     vis[v] = true;
     dist[v] = 0;
 
     for(i = 2; i <= n; i ++)
     {
         min = inf;
         for(j = 1; j <= n; j ++)
             if(!vis[j] && min > dist[j])
             {
                 min = dist[j];
                 u = j;
             }
 
         vis[u] = true;
 
         for(j = 1; j <= n; j ++)
             if(!vis[j] && dist[j] > dist[u] + cost[u][j])
                 dist[j] = dist[u] + cost[u][j];
     }
 
     if(dist[w] == inf)
         cout << "-1" << endl;
     else
         cout << dist[w] << endl;
 }
 
 int main()
 {
     int sp;
     int num;
     int len;
     int i,j;
     int cnt = 0;
     string start,destination;
     string begin,end;
 
     while(true)
     {
         cin >> num;
 
         if(num == -1)
             break;
 
         sp = 0;
         cnt = 0;
         treeMap.clear();
 
         cin >> start >> destination;
         if(!treeMap[start])
             {
                 cnt ++;
                 treeMap[start] = cnt;
             }
             if(!treeMap[destination])
             {
                 cnt ++;
                 treeMap[destination] = cnt;
             }
         
         for(i = 0; i < Size; i++)
             for(j = 0; j < Size; j++)
                 if(i == j)
                     cost[i][j] = 0;
                 else
                     cost[i][j] = inf;
 
         for(i = 1; i <= num; i ++)
         {
             cin >> begin >> end;
             if(!treeMap[begin])
             {
                 cnt ++;
                 treeMap[begin] = cnt;
             }
             if(!treeMap[end])
             {
                 cnt ++;
                 treeMap[end] = cnt;
             }
 
             cin >> len;
             cost[treeMap[end]][treeMap[begin]] = cost[treeMap[begin]][treeMap[end]] = len;
         }
 
         Dijkstra(treeMap[start], treeMap[destination], treeMap.size());
     }
 
     return 0;
 }

解题转自:http://www.cnblogs.com/coolwind-sea/archive/2012/08/18/2645600.html


  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.