题目详情
返回题库题目描述
终于放暑假了！
徐老师决定出去旅游，但是在出门旅游前他需要规划好所有的旅游路线
他一共打算去n个景点，他已经做好了景点之间的规划，一共有m条道路
对于旅游来说，路上的风景往往也非常有意义，所以徐老师打算规划一下在道路之间花费的时间
现在徐老师已经做了一个初步的规划，对于第i条道路来说，它连通的是$u_i,v_i$两个景点，徐老师初步打算在这条路上花费$cost_i$的时间
现在徐老师需要对道路规划进行进一步的优化：
只保留n-1条道路，只要保证通过这些道路，能确保徐老师能通过这些道路到达任意城市即可。（因为徐老师的目的是为了景点，在去过的景点之间频繁的来回穿梭并没有意义）
徐老师可以调整保留下来的道路上花费的时间，但是每次调整只能选择一条道路，然后给它的$cost_i+1$或者-1
最终徐老师希望保留下来的道路中最大的花费时间恰好为P
现在徐老师想知道，他最少需要调整几次？
输入描述
输入第一行包含两个整数n,m，表示景点数量和道路数量
接下来m行，每行包含三个整数$u_i,v_i,cost_i$表示一条道路的信息
最后一行包含一个整数P含义如题
数据范围
| 数据点编号 | 特殊性质 |
|---|---|
| $1 \sim 2$ | $cost_i \leq P$ |
| $3 \sim 4$ | $P \leq cost_i$ |
| $5 \sim 6$ | $n \leq 1000$ |
| $7 \sim 10$ | 无 |
对于所有数据满足$2 \leq n \leq 2 \times 10^5,n-1 \leq m \leq \min(2 \times 10^5,\frac{n(n-1)}{2}), 1 \leq u_i,v_i \leq n, 1 \leq cost_i,P \leq 10^9$
且保证$u_i \not= v_i$
输出描述
输出一个整数表示徐老师最少的调整次数
提示
样例解释1
其中一种方案为：保留第2,3,5三条道路，并且调整第3条道路$cost_i-1=7$
样例解释2
其中一种方案为：保留第2,3,4三条道路，并且将第3,4条道路各调整2次使得$cost_i-2=6$，一共需要调整4次