Skip to content

11269: 【原1269】最小差异值2

题目

题目描述

author: 黄宇扬 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1269

Description

前情提要:http://acm.sjtu.edu.cn/OnlineJudge/problem/1266

不久后,P省又发生了地震,因为省长治理有方,现在P省的规模变大了很多。

省长仍然希望最贵道路的价格和最便宜道路的价格的差值尽量小,请你尽快地安排一种合理的方案,满足省长的要求。

Input Format

输入共有两行。

第一行两个数N,M,表示城市的个数以及可以修的公路数;

第二行开始M行,每行三个数a,b,c,表示a,b之间可以修一条价值c的无向道路(可能有自环)。

70%数据满足N<=M<=5000

100%数据满足N<=M<=100000,0<c<=100000;

Output Format

一个数表示该方案中最大边减去最小边的值,要求要尽量的小。

Sample Input

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

Sample Output

1686

(选第4,5,6,9条边即可。)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!