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
; }
这道题在输入的处理还可以，但是没有对算法进行优化，毕竟新学的基础题。