prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem D: </font>Long Distance Taxi </H1>3 4<p>5A taxi driver, Nakamura, was so delighted because he got a passenger who wanted to go to a6city thousands of kilometers away. However, he had a problem. As you may know, most taxis in7Japan run on liquefied petroleum gas (LPG) because it is cheaper than gasoline. There are more8than 50,000 gas stations in the country, but less than one percent of them sell LPG. Although9the LPG tank of his car was full, the tank capacity is limited and his car runs 10 kilometer per10liter, so he may not be able to get to the destination without filling the tank on the way. He11knew all the locations of LPG stations.12Your task is to write a program that finds the best way from the current location to the destination without running out of gas.13</p>14 15<H2>Input</H2>16 17<p>18The input consists of several datasets, and each dataset is in the following format.19</p>20 21<p>22<i>N M cap<br>23src dest</i><br>24<i>c</i><sub>1,1</sub> <i>c</i><sub>1,2</sub> <i>d</i><sub>1</sub><br>25<i>c</i><sub>2,1</sub> <i>c</i><sub>2,2</sub> <i>d</i><sub>2</sub><br>26.<br>27.<br>28.<br>29<i>c</i><sub>N,1</sub> <i>c</i><sub>N,2</sub> <i>d</i><sub>N</sub><br>30<i>s</i><sub>1</sub><br>31<i>s</i><sub>2</sub><br>32.<br>33.<br>34.<br>35<i>s</i><sub>M</sub>36 37<p>38The first line of a dataset contains three integers (<i>N, M, cap</i>), where <i>N</i> is the number of roads39(1 &le; <i>N</i> &le; 3000),<i>M</i> is the number of LPG stations (1&le; <i>M</i> &le; 300), and <i>cap</i> is the tank capacity40(1 &le; <i>cap</i> &le; 200) in liter. The next line contains the name of the current city (<i>src</i>) and the name41of the destination city (<i>dest</i>). The destination city is always different from the current city.42The following <i>N</i> lines describe roads that connect cities. The road i (1 &le; <i>i</i> &le; N) connects two43different cities <i>c</i><sub>i,1</sub> and <i>c</i><sub>i,2</sub> with an integer distance <i>d</i><sub>i</sub> (0 &lt; <i>d</i><sub>i</sub> &le; 2000) in kilometer, and he can44go from either city to the other. You can assume that no two different roads connect the same45pair of cities. The columns are separated by a single space. The next <i>M</i> lines (<i>s</i><sub>1</sub>,<i>s</i><sub>2</sub>,...,<i>s</i><sub>M</sub>) indicate the names of the cities with LPG station. 46You can assume that a city with LPG station has at least one road.47</p>48 49<p>50The name of a city has no more than 15 characters. Only English alphabet ('A' to 'Z' and 'a'51to 'z', case sensitive) is allowed for the name.52</p>53 54<p>55A line with three zeros terminates the input.56</p>57 58<H2>Output</H2>59 60<p>61For each dataset, output a line containing the length (in kilometer) of the shortest possible62journey from the current city to the destination city. If Nakamura cannot reach the destination,63output "-1" (without quotation marks). You must not output any other characters.64The actual tank capacity is usually a little bit larger than that on the specification sheet, so65you can assume that he can reach a city even when the remaining amount of the gas becomes66exactly zero. In addition, you can always fill the tank at the destination so you do not have to67worry about the return trip.68</p>69 70<H2>Sample Input</H2>71<pre>726 3 3473Tokyo Kyoto74Tokyo Niigata 33575Tokyo Shizuoka 17476Shizuoka Nagoya 17677Nagoya Kyoto 19578Toyama Niigata 21579Toyama Kyoto 29680Nagoya81Niigata82Toyama836 3 3084Tokyo Kyoto85Tokyo Niigata 33586Tokyo Shizuoka 17487Shizuoka Nagoya 17688Nagoya Kyoto 19589Toyama Niigata 21590Toyama Kyoto 29691Nagoya92Niigata93Toyama940 0 095</pre>96 97<H2>Output for the Sample Input</H2>98<pre>99846100-1101</pre>