HDU Today

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13952 Accepted Submission(s): 3264

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

Input 输入数据有多组，每组的第一行是公交车的总数N(0<=N<=10000)；
第二行有徐总的所在地start，他的目的地end；
接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0 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 
   
    
#include 
     
     using namespace std
     ; #define min(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
      ; }

这道题在输入的处理还可以，但是没有对算法进行优化，毕竟新学的基础题。

HDU 2112 HDU Today (Dijkstra算法)

HDU Today