问题 4818 --3.最小差值

4818: 3.最小差值

题目描述

  给定一个无向图，求它的一棵生成树，使得生成树中的最大边权与最小边权的差最小，输出其最小差值。

输入

第一行两个整数 $n,m$，分别表示点数和边数。
接下来 $m$ 行，第 $i+1$ 行包含三个整数 $x_i,y_i,d_i$ ，表示有一条边连接 $x_i$ 和 $y_i$，距离为 $d_i$ 。

输出

包含一行，表示最小差值生成树的最大边与最小边的差值。

样例输入输出

输入#1 复制 
3 3
1 2 10
1 3 20
2 3 30
输出#1 复制 
10

提示

对于 $100\%$  的数据， $2\leq n \leq 200, 1 \leq m \leq 5000,0\le x_i,y_i \leq n, 0 \le d_i \leq 10^8  $。
保证图是连通的，两个点之间最多只有一条边。

发表题解
序号 标题 作者 发表时间 费用 订购数 操作

题目信息

提交
难度
未评定
标签
点击显示
递交数
3
已通过
3
通过率
100%
时间限制
1 秒
内存限制
256 MB
来源
2020CSP模拟A2
收藏