prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem G:</font> Test Case Tweaking</H1>3 4<p>5You are a judge of a programming contest. You are preparing a dataset for a graph problem to seek for the cost of the minimum cost path. You've generated some random cases, but they are not interesting. You want to produce a dataset whose answer is a desired value such as the number representing this year 2010. So you will tweak (which means 'adjust') the cost of the minimum cost path to a given value by changing the costs of some edges. The number of changes should be made as few as possible.6</p>7 8<p>9A non-negative integer c and a directed graph <i>G</i> are given. Each edge of <i>G</i> is associated with a cost of a non-negative integer. Given a path from one node of <i>G</i> to another, we can define the cost of the path as the sum of the costs of edges constituting the path. Given a pair of nodes in <i>G</i>, we can associate it with a non-negative cost which is the minimum of the costs of paths connecting them.10</p>11 12<p>13Given a graph and a pair of nodes in it, you are asked to adjust the costs of edges so that the minimum cost path from one node to the other will be the given target cost <i>c</i>. You can assume that <i>c</i> is smaller than the cost of the minimum cost path between the given nodes in the original graph.14</p>15 16<p>17For example, in Figure G.1, the minimum cost of the path from node 1 to node 3 in the given graph is 6. In order to adjust this minimum cost to 2, we can change the cost of the edge from node 1 to node 3 to 2. This direct edge becomes the minimum cost path after the change. 18</p>19 20<p>21For another example, in Figure G.2, the minimum cost of the path from node 1 to node 12 in the given graph is 4022. In order to adjust this minimum cost to 2010, we can change the cost of the edge from node 6 to node 12 and one of the six edges in the right half of the graph. There are many possibilities of edge modification, but the minimum number of modified edges is 2.22</p>23 24<H2>Input</H2>25 26<p>27The input is a sequence of datasets. Each dataset is formatted as follows.28</p>29 30<p>31<i>n m c</i><br>32<i>f</i><sub>1</sub> <i>t</i><sub>1</sub> <i>c</i><sub>1</sub><br>33<i>f</i><sub>2</sub> <i>t</i><sub>2</sub> <i>c</i><sub>2</sub><br>34.<br>35.<br>36.<br>37<i>f</i><sub><i>m</i></sub> <i>t</i><sub><i>m</i></sub> <i>c</i><sub><i>m</i></sub><br>38</p>39 40 41<center>42<table>43<tr>44<td><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_testCaseTweaking1"></td>45<td><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_testCaseTweaking2"></td>46</tr>47<tr>48<td align="center"><p>Figure G.1: Example 1 of graph</p></td>49<td align="center"><p>Figure G.2: Example 2 of graph</p></td>50</tr>51</table>52</center>53 54<p>55The integers <i>n</i>, <i>m</i> and <i>c</i> are the number of the nodes, the number of the edges, and the target cost, respectively, each separated by a single space, where 2 &le; <i>n</i> &le; 100, 1 &le; <i>m</i> &le; 1000 and 0 &le; <i>c</i> &le; 100000.56</p>57 58<p>59Each node in the graph is represented by an integer 1 through <i>n</i>.60</p>61 62<p>63The following <i>m</i> lines represent edges: the integers <i>f<sub>i</sub></i>, <i>t<sub>i</sub></i> and <i>c<sbu>i</sub></i> (1 &le; <i>i</i> &le; <i>m</i>) are the originating node, the destination node and the associated cost of the <i>i</i>-th edge, each separated by a single space. They satisfy 1 &le; <i>f<sub>i</sub></i>, <i>t<sub>i</sub></i> &le; <i>n</i> and 0 &le; <i>c<sub>i</sub></i> &le; 10000. You can assume that <i>f<sub>i</sub></i> &ne; <i>t<sub>i</sub></i> and (<i>f<sub>i</sub></i>, <i>t<sub>i</sub></i>) &ne; (<i>f<sub>j</sub></i>, <i>t<sub>j</sub></i>) when <i>i</i> &ne; <i>j</i>.64</p>65 66<p>67You can assume that, for each dataset, there is at least one path from node 1 to node <i>n</i>, and that the cost of the minimum cost path from node 1 to node <i>n</i> of the given graph is greater than <i>c</i>.68</p>69 70<p>71The end of the input is indicated by a line containing three zeros separated by single spaces.72</p>73 74 75<H2>Output</H2>76 77<p>78For each dataset, output a line containing the minimum number of edges whose cost(s) should be changed in order to make the cost of the minimum cost path from node 1 to node <i>n</i> equal to the target cost <i>c</i>. Costs of edges cannot be made negative. The output should not contain any other extra characters.79</p>80 81<H2>Sample Input</H2>82<pre>833 3 3841 2 3852 3 3861 3 88712 12 2010881 2 0892 3 3000903 4 0914 5 3000925 6 3000936 12 2010942 7 100957 8 200968 9 300979 10 4009810 11 5009911 6 51210010 18 11011 2 91021 3 21031 4 61042 5 01052 6 101062 7 21073 5 101083 6 31093 7 101104 7 61115 8 101126 8 21136 9 111147 9 31158 9 91168 10 81179 10 11188 2 11190 0 0120</pre>121 122<H2>Output for the Sample Input</H2>123<pre>124112521263127</pre>128 129