prithivMLmods/Coder-Stat

1 2<h1><font color="#000">Problem D:</font> Traveling by Stagecoach</h1>3 4<p>5Once upon a time, there was a traveler.6</p>7 8<p>9He plans to travel using stagecoaches (horse wagons).10His starting point and destination are fixed,11but he cannot determine his route.12Your job in this problem is to write a program13which determines the route for him.14</p>15 16<p>17There are several cities in the country,18and a road network connecting them.19If there is a road between two cities, one can travel by a stagecoach20from one of them to the other.21A coach ticket is needed for a coach ride.22The number of horses is specified in each of the tickets.23Of course, with more horses, the coach runs faster.24</p>25 26<p>27At the starting point, the traveler has a number of coach tickets.28By considering these tickets and the information on the road network,29you should find the best possible route that takes him to the destination30in the shortest time.31The usage of coach tickets should be taken into account.32</p>33 34<p>35The following conditions are assumed.36</p>37 38<ul><li> A coach ride takes the traveler from one city to another 39directly connected by a road.40In other words, on each arrival to a city, he must change the coach. </li>41<li> Only one ticket can be used for a coach ride between two cities42directly connected by a road. </li>43<li> Each ticket can be used only once. </li>44<li> The time needed for a coach ride is the distance between two cities45divided by the number of horses. </li>46<li> The time needed for the coach change should be ignored. </li></ul>47 48<h2>Input</h2>49 50<p>51The input consists of multiple datasets, each in the following format.52The last dataset is followed by a line containing five zeros53(separated by a space).54</p>55 56<blockquote>57<i>n m p a b</i><br>58<i>t</i><sub>1</sub> <i>t</i><sub>2</sub> ... <i>t<sub>n</sub></i><br>59<i>x</i><sub>1</sub> <i>y</i><sub>1</sub> <i>z</i><sub>1</sub><br>60<i>x</i><sub>2</sub> <i>y</i><sub>2</sub> <i>z</i><sub>2</sub><br>61...<br>62<i>x<sub>p</sub></i> <i>y<sub>p</sub></i> <i>z<sub>p</sub></i><br>63</blockquote>64 65<p>66Every input item in a dataset is a non-negative integer.67If a line contains two or more input items, they are separated by a space.68</p>69 70<p>71<i>n</i> is the number of coach tickets.72You can assume that the number of tickets is between 1 and 8.73<i>m</i> is the number of cities in the network.74You can assume that the number of cities is between 2 and 30.75<i>p</i> is the number of roads between cities, which may be zero.76</p>77 78<p>79<i>a</i> is the city index of the starting city.80<i>b</i> is the city index of the destination city.81<i>a</i> is not equal to <i>b</i>.82You can assume that all city indices in a dataset (including the above two)83are between 1 and <i>m</i>.84</p>85 86<p>87The second line of a dataset gives the details of coach tickets.88<i>t<sub>i</sub></i> is the number of horses specified in the <i>i</i>-th89coach ticket (1&lt;=<i>i</i>&lt;=<i>n</i>).90You can assume that the number of horses is between 1 and 10.91</p>92 93<p>94The following <i>p</i> lines give the details of roads between cities.95The <i>i</i>-th road connects two cities with city indices96<i>x<sub>i</sub></i> and <i>y<sub>i</sub></i>,97and has a distance <i>z<sub>i</sub></i> (1&lt;=<i>i</i>&lt;=<i>p</i>).98You can assume that the distance is between 1 and 100.99</p>100 101<p>102No two roads connect the same pair of cities.103A road never connects a city with itself.104Each road can be traveled in both directions.105</p>106 107<h2>Output</h2>108 109<p> 110For each dataset in the input, one line should be output as specified below.111An output line should not contain extra characters such as spaces.112</p>113 114<p>115If the traveler can reach the destination, the time needed116for the best route (a route with the shortest time) should be printed.117The answer should not have an error greater than 0.001.118You may output any number of digits after the decimal point,119provided that the above accuracy condition is satisfied.120</p>121 122<p>123If the traveler cannot reach the destination,124the string "<tt>Impossible</tt>" should be printed.125One cannot reach the destination either when there are no routes126leading to the destination, or when the number of tickets is not sufficient.127Note that the first letter of "<tt>Impossible</tt>" is in uppercase,128while the other letters are in lowercase.129</p>130 131<h2>Sample Input</h2>132<pre>1333 4 3 1 41343 1 21351 2 101362 3 301373 4 201382 4 4 2 11393 11402 3 31411 3 31424 1 21434 2 51442 4 3 4 11455 51461 2 101472 3 101483 4 101491 2 0 1 215011518 5 10 1 51522 7 1 8 4 5 6 31531 2 51542 3 41553 4 71564 5 31571 3 251582 4 231593 5 221601 4 451612 5 511621 5 991630 0 0 0 0164</pre>165 166<h2>Output for the Sample Input</h2>167<pre>16830.0001693.667170Impossible171Impossible1722.856173</pre>174 175 176 177<!--178<p>179Since the number of digits after the decimal point is not specified,180the above result is not the only solution.181For example, the following result is also acceptable.182</p>183 184<pre>18530.01863.66667187Impossible188Impossible1892.85595190</pre>191-->192 193 194