prithivMLmods/Coder-Stat

1 2<h1><font color="#000000">Problem D:</font> Discrete Speed</h1>3 4 5<p>6Consider car trips in a country where there is no friction.7Cars in this country do not have engines.8Once a car started to move at a speed, it keeps moving at the same speed.9There are acceleration devices on some points on the road,10where a car can increase or decrease its speed by 1.11It can also keep its speed there.12Your job in this problem is to write a program13which determines the route with the shortest time14to travel from a starting city to a goal city.15</p>16 17<p>18There are several cities in the country,19and a road network connecting them.20Each city has an acceleration device.21As mentioned above, if a car arrives at a city at a speed <i>v </i>,22it leaves the city at one of <i>v </i>- 1, <i>v </i>, or <i>v </i>+ 1.23The first road leaving the starting city must be run at the speed 1.24Similarly, the last road arriving at the goal city must be run at the speed 1.25 26</p>27 28<p>29The starting city and the goal city are given.30The problem is to find the best route which leads to the goal city31going through several cities on the road network.32When the car arrives at a city, it cannot immediately go back the road33it used to reach the city.  No U-turns are allowed.34Except this constraint, one can choose any route on the road network.35It is allowed to visit the same city or use the same road multiple times.36The starting city and the goal city may be visited during the trip.37</p>38 39<p>40For each road on the network, its distance and speed limit are given.41A car must run a road at a speed less than or equal to its speed limit.42The time needed to run a road is the distance divided by the speed.43The time needed within cities including that for acceleration or deceleration should be ignored. </li></ul>44 45 46<h3>Input</h3>47 48<p>49The input consists of multiple datasets, each in the following format.50</p>51 52 53<blockquote>54<i>n </i> <i>m </i><br>55<i>s </i> <i>g </i><br>56 57<i>x</i><sub> 1</sub> <i>y</i><sub> 1</sub> <i>d</i><sub> 1</sub> <i>c</i><sub> 1</sub><br>58...<br>59 60<i>x<sub>m</sub> </i> <i>y<sub>m</sub> </i> <i>d<sub>m</sub> </i> <i>c<sub>m</sub> </i><br>61</blockquote>62 63<!-- begin en only -->64<p>65Every input item in a dataset is a non-negative integer.66Input items in the same line are separated by a space.67</p>68 69<p>70The first line gives the size of the road network.71<i>n </i> is the number of cities in the network.72You can assume that the number of cities is between 2 and 30, inclusive.73<i>m </i> is the number of roads between cities, which may be zero.74</p>75 76<p>77 78The second line gives the trip.79<i>s </i> is the city index of the starting city.80<i>g </i> is the city index of the goal city.81<i>s </i> is not equal to <i>g </i>.82You can assume that all city indices in a dataset (including the above two)83are between 1 and <i>n </i>, inclusive.84</p>85 86<p>87 88The following <i>m </i> lines give the details of roads between cities.89The <i>i </i>-th road connects two cities with city indices90<i>x<sub>i</sub> </i> and <i>y<sub>i</sub> </i>,91and has a distance <i>d<sub>i</sub> </i> (1 &le; <i>i </i>&le; <i>m </i>).92You can assume that the distance is between 1 and 100, inclusive.93The speed limit of the road is specified by <i>c<sub>i</sub> </i>.94You can assume that the speed limit is between 1 and 30, inclusive.95 96</p>97 98<p>99No two roads connect the same pair of cities.100A road never connects a city with itself.101Each road can be traveled in both directions.102</p>103 104<p>105The last dataset is followed by a line containing two zeros106(separated by a space).107</p>108 109 110 111 112<h3>Output</h3>113 114<p> 115For each dataset in the input, one line should be output as specified below.116An output line should not contain extra characters such as spaces.117</p>118 119<p>120If one can travel from the starting city to the goal city,121the time needed for the best route (a route with the shortest time)122should be printed.123The answer should not have an error greater than 0.001.124You may output any number of digits after the decimal point,125provided that the above accuracy condition is satisfied.126</p>127 128<p>129If it is impossible to reach the goal city,130the string "<tt>unreachable</tt>" should be printed.131Note that all the letters of "<tt>unreachable</tt>" are in lowercase.132 133</p>134 135 136<h3>Sample Input</h3>137 138 139<pre>1402 01411 21425 41431 51441 2 1 11452 3 2 21463 4 2 21474 5 1 11486 61491 61501 2 2 11512 3 2 11523 6 2 11531 4 2 301544 5 3 301555 6 2 301566 71571 61581 2 1 301592 3 1 301603 1 1 301613 4 100 301624 5 1 301635 6 1 301646 4 1 301650 0166</pre>167 168<h3>Output for the Sample Input</h3>169 170 171<pre>172unreachable1734.000001745.5000017511.25664176</pre>177 178 179