prithivMLmods/Coder-Stat

1 2<h1>Railway Connection</h1>3<!-- end en only -->4 5 6<!-- begin en only -->7<p>8Tokyo has a very complex railway system.9For example, there exists a partial map of lines and stations10as shown in Figure D-1.11</p>12<!-- end en only -->13 14 15<center>16<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_1182_1" align="center" width="300"><br><br>17<!-- begin en only -->18Figure D-1: A sample railway network19<!-- end en only -->20<br>21</center>22 23<!-- begin en only -->24<p>25Suppose you are going to station D from station A.26Obviously, the path with the shortest distance is A&rarr;B&rarr;D.27However, the path with the shortest distance does not necessarily28mean the minimum cost.29Assume the lines A-B, B-C, and C-D are operated by one railway company,30and the line B-D is operated by another company.31In this case, the path A&rarr;B&rarr;C&rarr;D may cost less than A&rarr;B&rarr;D.32One of the reasons is that the fare is not proportional to the distance.33Usually, the longer the distance is, the fare per unit distance is lower.34If one uses lines of more than one railway company,35the fares charged by these companies are simply added together,36and consequently the total cost may become higher although the distance is shorter37than the path using lines of only one company.38</p>39<!-- end en only -->40 41 42<!-- begin en only -->43<p>44In this problem, a railway network including multiple railway companies is given.45The fare table (the rule to calculate the fare from the distance) of each company is also given.46Your task is, given the starting point and the goal point, to write a program47that computes the path with the least total fare.48</p>49<!-- end en only -->50 51 52 53<h3>Input</h3>54 55 56 57<!-- begin en only -->58<p>59The input consists of multiple datasets, each in the following format.60</p>61<!-- end en only -->62 63 64<blockquote>65<i>n</i> <i>m</i> <i>c</i> <i>s</i> <i>g</i><br>66<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>67...<br>68<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>69<i>p</i><sub>1</sub> ... <i>p<sub>c</sub></i><br>70<i>q</i><sub>1,1</sub> ... <i>q</i><sub>1,<i>p</i><sub>1</sub>-1</sub><br>71<i>r</i><sub>1,1</sub> ... <i>r</i><sub>1,<i>p</i><sub>1</sub></sub><br>72...<br>73<i>q</i><sub><i>c</i>,1</sub> ... <i>q</i><sub><i>c,p</i><sub><i>c</i></sub>-1</sub><br>74<i>r</i><sub><i>c</i>,1</sub> ... <i>r</i><sub><i>c,p<sub>c</sub></i></sub><br>75</blockquote>76 77<!-- begin en only -->78<p>79Every input item in a dataset is a non-negative integer.80Input items in the same input line are separated by a space.81</p>82<!-- end en only -->83 84 85<!-- begin en only -->86<p>87The first input line gives the size of the railway network and the intended trip.88<i>n </i> is the number of stations (2 &le; <i>n</i> &le; 100).89<i>m </i> is the number of lines connecting two stations (0 &le; <i>m</i> &le; 10000).90<i>c </i> is the number of railway companies (1 &le; <i>c</i> &le; 20).91<i>s </i> is the station index of the starting point (1 &le; <i>s</i> &le; <i>n</i> ).92<i>g </i> is the station index of the goal point (1 &le; <i>g</i> &le; <i>n</i>, <i>g</i> &ne; <i>s</i> ).93</p>94<!-- end en only -->95 96 97<!-- begin en only -->98<p>99The following <i>m </i> input lines give the details of (railway) lines.100The <i>i </i>-th line connects two stations101<i>x<sub>i</sub> </i> and <i>y<sub>i</sub> </i>102(1 &le; <i>x<sub>i</sub></i> &le; <i>n</i>,1031 &le; <i>y<sub>i</sub></i> &le; <i>n</i>,104<i>x<sub>i</sub></i> &ne; <i>y<sub>i</sub></i> ).105Each line can be traveled in both directions.106There may be two or more lines connecting the same pair of stations.107<i>d<sub>i</sub> </i> is the distance of the <i>i </i>-th line (1 &le; <i>d<sub>i</sub></i> &le; 200).108<i>c<sub>i</sub> </i> is the company index of the railway company operating the line (1 &le; <i>c<sub>i</sub></i> &le; <i>c</i> ).109</p>110<!-- end en only -->111 112 113<!-- begin en only -->114<p>115The fare table (the relation between the distance and the fare)116of each railway company can be expressed as a line chart.117For the railway company <i>j </i>,118the number of sections of the line chart is given by <i>p<sub>j</sub> </i>119(1 &le; <i>p<sub>j</sub></i> &le; 50).120<i>q<sub>j,k</sub> </i> (1 &le; <i>k</i> &le; <i>p<sub>j</sub></i>-1) gives121the distance separating two sections of the chart122(1 &le; <i>q<sub>j,k</sub></i> &le; 10000).123<i>r<sub>j,k</sub> </i> (1 &le; <i>k</i> &le; <i>p<sub>j</sub></i> ) gives124the fare increment per unit distance for the corresponding section of the chart125(1 &le; <i>r<sub>j,k</sub></i> &le; 100).126More precisely, with the fare for the distance <i>z </i> denoted by127<i>f<sub>j</sub></i> (<i>z</i> ),128the fare for distance <i>z </i> satisfying129<i>q</i><sub><i>j</i>,<i>k</i>-1</sub>+1 &le; <i>z</i> &le; <i>q</i><sub><i>j</i>,<i>k</i></sub> 130is computed by the recurrence relation131<i>f<sub>j</sub></i> (<i>z</i>) = <i>f<sub>j</sub></i> (<i>z</i>-1)+<i>r<sub>j,k</sub></i>.132Assume that <i>q</i><sub><i>j</i>,0</sub> and <i>f<sub>j</sub></i> (0) are zero,133and <i>q</i><sub><i>j</i>,<i>p<sub>j</sub></i></sub> is infinity.134</p>135<!-- end en only -->136 137 138<!-- begin en only -->139<p>140For example, assume <i>p<sub>j</sub> </i> = 3,141<i>q</i><sub><i>j</i>,1</sub> = 3,142<i>q</i><sub><i>j</i>,2</sub> = 6,143<i>r</i><sub><i>j</i>,1</sub> = 10,144<i>r</i><sub><i>j</i>,2</sub> = 5, and145<i>r</i><sub><i>j</i>,3</sub> = 3.146The fare table in this case is as follows.147</p>148 149<table border=1>150<tr align=right><td>distance</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td></tr>151<tr align=right><td>fare</td><td>10</td><td>20</td><td>30</td><td>35</td><td>40</td><td>45</td><td>48</td><td>51</td><td>54</td></tr>152</table>153<!-- end en only -->154 155 156<!-- begin en only -->157<p>158<i>q<sub>j,k</sub> </i> increase monotonically with respect to <i>k </i>.159<i>r<sub>j,k</sub> </i> decrease monotonically with respect to <i>k </i>.160</p>161<!-- end en only -->162 163 164<!-- begin en only -->165<p>166The last dataset is followed by an input line containing five zeros167(separated by a space).168</p>169<!-- end en only -->170 171 172 173 174<h3>Output</h3>175 176 177 178<!-- begin en only -->179<p> 180For each dataset in the input, the total fare for the best route181(the route with the minimum total fare)182should be output as a line.183If the goal cannot be reached from the start, output &quot;-1&quot;.184An output line should not contain extra characters such as spaces.185</p>186<!-- end en only -->187 188 189<!-- begin en only -->190<p>191Once a route from the start to the goal is determined,192the total fare of the route is computed as follows.193If two or more lines of the same railway company are used contiguously,194the total distance of these lines is used to compute the fare of this section.195The total fare of the route is the sum of fares of such "sections consisting196of contiguous lines of the same company".197Even if one uses two lines of the same company, if a line of another company198is used between these two lines, the fares of sections including these two199lines are computed independently.200No company offers transit discount.201</p>202<!-- end en only -->203 204 205 206 207<h3>Sample Input</h3>208 209 210<pre>2114 4 2 1 42121 2 2 12132 3 2 12143 4 5 12152 4 4 22163 12173 621810 5 3219 220102212 0 1 1 22221223 22412254 5 2 4 12264 3 10 12273 2 2 12283 2 1 22293 2 5 22302 1 10 12313 323220 302333 2 12345 102353 2 12365 5 2 1 52371 2 10 22381 3 20 22392 4 20 12403 4 10 12414 5 20 12422 2243202444 1245202463 12470 0 0 0 0248</pre>249 250 251<h3>Output for the Sample Input</h3>252 253 254<pre>25554256-125763258130259</pre>