![]() |
||||||||||
|
||||||||||
大四狗的毕业旅行Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1 Accepted Submission(s): 1 Problem Description 又快到大四狗组织毕业旅行的时候了,以前都是屌丝似得坐着火车去,这次来点高大上的,我们自驾游去。 但是现在有个问题是这次去的地方比较偏僻,比如撒哈拉大沙漠(O(∩_∩)~,),那里的加油站距离都很远。如果我们从一个城市到另外一个城市突然在路上没有油了,那不就悲剧了,因此这样的情况是不能出现的。 现在我们想知道从始发地到目的地最短行驶的距离。(假设每升油可以跑$10$公里) Input 输入格式如下: $N \quad M \quad cap$ $src \quad dest$ $c_{1, 1} \quad c_{1, 2} \quad d_1$ $c_{2, 1} \quad c_{2, 2} \quad d_2$ $...$ $c_{N, 1} \quad c_{N, 2} \quad d_N$ $s_1$ $s_2$ $...$ $s_M$ 第一行三个整数$(N , M , cap),N$表示有多少条路$(1 \leq N \leq 3000), M$是有多少个加油站$(1 \leq M \leq 300)$, and cap 表示车的容量(单位:升)$(1 \leq cap \leq 200)$ . 第二行表示始发地和目的地,保证不相同。下面有$N$行,表示$N$条路,第$ i (1 \leq i \leq N)$ 条路连接城市$C_i,1$和$C_i,2$,两城市的距离是$D_i (0 < D_i \leq 2000)$公里。接着是$M$行$(S_1, S_2, . . . , S_m)$表示各加油站的名字. 保证所有的加油站之间都是可达的。 城市名不会超过$15$字符,且仅包含英文字母。 当输入$3$个$0$时,程序结束。 Output 输出从始发地到目的地最短的距离,如果不可达, 输出$-1$。 Sample Input
Sample Output
Source | ||||||||||
|