有时非常郁闷。想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（事实上徐总自己有车。却一定要与民同乐，这就是徐总的性格）。 徐总常常会问蹩脚的英文问路：“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 尽管偶尔会迷路。可是由于有了你的帮助 **和**从此还是过上了幸福的生活。 ――全剧终―― Author lgx Source ACM程序设计_期末考试（时间已定！！）
Recommend lcy | We have carefully selected several similar problems for you: 1874 1217 2680 1142 1385 主要是前期处理困难啊。只是还是想办法搞定了。 代码：859MS (代码没优化) #include <iostream> #include <string> using namespace std; #define min(a,b) (a<b?a:b) #define max(a,b) (a>b?a:b) #define M 160 #define INF 0xfffff;
int dis [M ],map [M ][M ],n ; char a [M ][M ]; int find (char s []) { int i ; for(i = 1 ;i <=n ;i ++) if(strcmp (s ,a [i ])== 0 ) //假设已经出现过，就直接用下标。 return i ; strcpy (a [++n ],s ); //没有出现过，就将点增加，总站数+1，该网站下标为n+1。 return n ; //将现有的网站数返回。 } void Dijkstra (int x ) //模板。 { bool v [M ]; int i ,j ,k ,minx ; memset (v , 0 ,sizeof(v )); for(i = 1 ;i <=n ;i ++) dis [i ]=map [x ][i ]; v [x ]= 1 ; for(i = 1 ;i <n ;i ++) { minx =INF ; for(j = 1 ;j <=n ;j ++) //找到当前能够确定是最短路径的点。 Dijkstra的核心（贪心）。 if (!v [j ] && dis [j ]<minx ) { k =j ; minx =dis [j ]; } v [k ]= 1 ; minx =INF ; for(j = 1 ;j <=n ;j ++) //更新权值，也就是当前的最短路更新。 if(!v [j ] && dis [k ]<minx ) { dis [j ]=min (dis [j ],dis [k ]+map [k ][j ]); } } } int main() { int N ; while(scanf ( "%d" ,&N ),N !=- 1 ) { char s [M ];int r =INF ; int start ,end ,a ,b ,time ,i ,j ; n = 0 ; cin >> s ; start = find (s ); cin >> s ; end = find (s ); for(i = 0 ;i <M ;i ++) for(j = 0 ;j <M ;j ++) map [i ][j ] = (i ==j ? 0 :r ); for(i = 0 ;i <N ;i ++) { cin >>s ; a =find (s ); cin >>s ; b =find (s ); cin >>time ; map [a ][b ]=map [b ][a ]=min (map [a ][b ],time ); } Dijkstra (start ); if(dis [end ]!=r ) cout <<dis [end ]<<endl ; else if(start ==end ) cout << "0" <<endl ; else cout << "-1" <<endl ; } return 0 ; } 这问题，也可以在输入处理。但是，没有优化算法，新学校学科的基础后，。版权声明：本文博主原创文章。博客，未经同意不得转载。
转载于:https://www.cnblogs.com/bhlsheji/p/4887996.html
