难敲杯国决终于结束了!好不容易来一趟京城,一行人决定去观光旅游景点,他们选择了一些必须要去的名胜。但是队长 HYR 的认路能力实在信不过,于是 Dr.Su 把安排路线的任务交给号称“人形自走 GPS”的 CGY。可是 CGY 第二天要去和自己的高中同学聚会,所以安排的路线规划必须尽可能的简单以使得路痴队长 HYR 能记住。
以下是 HYR 的要求:在能到达所有景点的基础上,选择尽可能少的道路,以便他记住的道路条数尽可能少。在此基础上,为了保证心理差距不要太大,路的长度区间必须尽可能的小,即要求最长的路和最短的路的长度差最小。
CGY 忙于联系自己的高中基友,并没有足够的时间搞这个,于是又把任务丢给了你,并答应事成之后请你喝北京名特产豆汁儿。
输入
输入包括多组样例(保证 1 \leq T≤1000),直到输入 0 0
为止。
每组样例格式如下:
n \ m
A_1 \ B_1 \ W_1
... \ ... \ ...
A_m \ B_m \ W_m
其中,所有输入均为整数,n \ (2≤n≤100) 表示景点个数,m \ (0≤m≤ \frac{n \times (n-1)}{2}) 表示可选道路数量。A_i,B_i \ (1 \leq n \leq n) 表示第 i 条边连接的两个景点序号。W_i \ (1 \leq W_i≤10000) 表示第 i 条道路的长度。输入保证不存在自环边(连接同一个景点的道路)或平行边(两条连接同样两个景点的道路)。
输出
对于每组样例,如果能找到这种路线规划,则输出最长的路和最短的路的长度差。否则,输出 -1。
样例
标准输入 复制文本 |
4 5 1 2 3 1 3 5 1 4 6 2 4 6 3 4 7 4 6 1 2 10 1 3 100 1 4 90 2 3 20 2 4 80 3 4 40 2 1 1 2 1 3 0 3 1 1 2 1 3 3 1 2 2 2 3 5 1 3 6 5 10 1 2 110 1 3 120 1 4 130 1 5 120 2 3 110 2 4 120 2 5 130 3 4 120 3 5 110 4 5 120 5 10 1 2 9384 1 3 887 1 4 2778 1 5 6916 2 3 7794 2 4 8336 2 5 5387 3 4 493 3 5 6650 4 5 1422 5 8 1 2 1 2 3 100 3 4 100 4 5 100 1 5 50 2 5 50 3 5 50 4 1 150 0 0 |
标准输出 复制文本 |
1 20 0 -1 -1 1 0 1686 50 |
来源
2018 软件学院蓝桥杯热身赛 (For 16/17)