prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem F:</font> Slim Span</H1>3 4<p>5Given an undirected weighted graph <i>G</i>, you should find one of spanning trees specified as follows.6</p>7<p>8The graph <i>G</i> is an ordered pair (<i>V</i>, <i>E</i>), where <i>V</i> is a set of vertices {<i>v</i><sub>1</sub>, <i>v</i><sub>2</sub>, ... , <i>v<sub>n</sub></i>} and <i>E</i> is a set of undirected edges {<i>e</i><sub>1</sub>, <i>e</i><sub>2</sub>, ... , <i>e<sub>m</sub></i>}. Each edge <i>e</i> &isin; <i>E</i> has its weight <i>w</i>(<i>e</i>).9</p>10 11<p>12A spanning tree <i>T</i> is a tree (a connected subgraph without cycles) which connects all the n13vertices with <i>n</i> - 1 edges. The <i>slimness</i> of a spanning tree <i>T</i> is defined as the difference between14the largest weight and the smallest weight among the <i>n</i> - 1 edges of <i>T</i>.15</p>16 17<center>18<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_slimSpan1">19<p>20Figure 5: A graph <i>G</i> and the weights of the edges21</p>22</center>23 24<p>25For example, a graph <i>G</i> in Figure 5(a) has four vertices {<i>v</i><sub>1</sub>, <i>v</i><sub>2</sub>, <i>v</i><sub>3</sub>, <i>v</i><sub>4</sub>} and five undirected edges {<i>e</i><sub>1</sub>, <i>e</i><sub>2</sub>, <i>e</i><sub>3</sub>, <i>e</i><sub>4</sub>, <i>e</i><sub>5</sub>}. The weights of the edges are <i>w</i>(<i>e</i><sub>1</sub>) = 3, <i>w</i>(<i>e</i><sub>2</sub>) = 5, <i>w</i>(<i>e</i><sub>3</sub>) = 6, <i>w</i>(<i>e</i><sub>4</sub>) = 6, <i>w</i>(<i>e</i><sub>5</sub>) = 7 as shown in Figure 5(b).26</p>27 28 29<center>30<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_slimSpan2">31<p>32Figure 6: Examples of the spanning trees of <i>G</i>33</p>34</center>35 36<p>37There are several spanning trees for <i>G</i>. Four of them are depicted in Figure 6(a)-(d). The spanning tree <i>T</i><sub>a</sub> in Figure 6(a) has three edges whose weights are 3, 6 and 7. The largest weight38is 7 and the smallest weight is 3 so that the slimness of the tree <i>T</i><sub>a</sub> is 4. The slimnesses of39spanning trees <i>T</i><sub>b</sub> , <i>T</i><sub>c</sub> and <i>T</i><sub>d</sub> shown in Figure 6(b), (c) and (d) are 3, 2 and 1, respectively. You40can easily see the slimness of any other spanning tree is greater than or equal to 1, thus the41spanning tree <i>T</i><sub>d</sub> in Figure 6(d) is one of the slimmest spanning trees whose slimness is 1.42</p>43<p>44Your job is to write a program that computes the smallest slimness.45</p>46 47 48 49<H2>Input</H2>50 51<p>52The input consists of multiple datasets, followed by a line containing two zeros separated by a space. Each dataset has the following format.53</p>54 55<pre>56<i>n     m</i>57<i>a</i><sub>1</sub>  <i>b</i><sub>1</sub>  <i>w</i><sub>1</sub>58  .59  .60  .61<i>a</i><sub><i>m</i></sub>  <i>b</i><sub><i>m</i></sub>  <i>w</i><sub><i>m</i></sub>62</pre>63 64<p>65Every input item in a dataset is a non-negative integer. Items in a line are separated by a space.66</p>67 68<p>69<i>n</i> is the number of the vertices and m the number of the edges. You can assume 2 &le; <i>n</i> &le; 100 and 0 &le; <i>m</i> &le; <i>n</i>(<i>n</i> - 1)/2. <i>a<sub>k</sub></i> and <i>b<sub>k</sub></i> (<i>k</i> = 1, ... , <i>m</i>) are positive integers less than or equal to <i>n</i>, which represent the two vertices <i>v<sub>a<sub>k</sub></sub></i> and <i>v<sub>b<sub>k</sub></sub></i> connected by the <i>k</i>th edge <i>e<sub>k</sub></i>. <i>w<sub>k</sub></i> is a positive integer less than or equal to 10000, which indicates the weight of <i>e<sub>k</sub></i> . You can assume that the graph <i>G</i> = (<i>V</i>, <i>E</i>) is simple, that is, there are no self-loops (that connect the same vertex) nor parallel edges (that are two or more edges whose both ends are the same two vertices).70</p>71 72<H2>Output</H2>73 74<p>75For each dataset, if the graph has spanning trees, the smallest slimness among them should be76printed. Otherwise, <span>-1</span> should be printed. An output should not contain extra characters.77 78</p>79 80<H2>Sample Input</H2>81<pre>824 5831 2 3841 3 5851 4 6862 4 6873 4 7884 6891 2 10901 3 100911 4 90922 3 20932 4 80943 4 40952 1961 2 1973 0983 1991 2 11003 31011 2 21022 3 51031 3 61045 101051 2 1101061 3 1201071 4 1301081 5 1201092 3 1101102 4 1201112 5 1301123 4 1201133 5 1101144 5 1201155 101161 2 93841171 3 8871181 4 27781191 5 69161202 3 77941212 4 83361222 5 53871233 4 4931243 5 66501254 5 14221265 81271 2 11282 3 1001293 4 1001304 5 1001311 5 501322 5 501333 5 501344 1 1501350 0136</pre>137 138<H2>Output for the Sample Input</H2>139<pre>1401141201420143-1144-114511460147168614850149</pre>150 151 152 153 154