A6283. Welcome24ever 和水坑
编程题
普及+/提高
知识点
题目描述
天地之初，IOI 还只是遥远的梦想。
Welcome24ever 生活的地方有 $N$ 个水坑，编号为 $0, 1, \dots, N-1$，有 $M$ 条双向小路连接这些水坑。
每两个水坑之间**至多有一条路径**（路径包含一条或多条小路）可以互相到达，因此这些小路形成了一片森林；有些水坑之间根本无法互通（即 $M \le N-1$）。
Welcome24ever 走过每条小路需要一个固定的天数，不同的小路所需的时间可能不同。
他的朋友 fangz 想要新修 $N - M - 1$ 条小路，使得新修完成后，Welcome24ever 可以在**任意两个水坑之间互相到达**（也就是整个图连通）。
fangz 可以在任意两个水坑之间修路，Welcome24ever 通过**每一条新路**的时间都是 $L$ 天。
fangz 希望找到一种修路方式，使得修完之后，从任意一个水坑到另一个水坑的最短路时间中的**最大值**尽可能小（也就是让“直径”尽量小）。
Welcome24ever 生活的地方有 $N$ 个水坑，编号为 $0, 1, \dots, N-1$，有 $M$ 条双向小路连接这些水坑。
每两个水坑之间**至多有一条路径**（路径包含一条或多条小路）可以互相到达，因此这些小路形成了一片森林；有些水坑之间根本无法互通（即 $M \le N-1$）。
Welcome24ever 走过每条小路需要一个固定的天数，不同的小路所需的时间可能不同。
他的朋友 fangz 想要新修 $N - M - 1$ 条小路，使得新修完成后，Welcome24ever 可以在**任意两个水坑之间互相到达**（也就是整个图连通）。
fangz 可以在任意两个水坑之间修路，Welcome24ever 通过**每一条新路**的时间都是 $L$ 天。
fangz 希望找到一种修路方式，使得修完之后，从任意一个水坑到另一个水坑的最短路时间中的**最大值**尽可能小（也就是让“直径”尽量小）。
输入格式
- 第 $1$ 行：三个整数 $N, M, L$：
- $N$ —— 水坑的数量；
- $M$ —— 原本存在的小路数量；
- $L$ —— 每条新修小路的通过时间。
- 第 $2$ 行到第 $M+1$ 行：每行三个整数 $A[i], B[i], T[i]$，表示一条现有的小路：
- 小路连接水坑 $A[i]$ 和水坑 $B[i]$；
- 通过这条小路需要 $T[i]$ 天。
水坑编号为 $0 \sim N-1$。
原图中任意两点之间至多存在一条简单路径（即原图是一个森林）。
- $N$ —— 水坑的数量；
- $M$ —— 原本存在的小路数量；
- $L$ —— 每条新修小路的通过时间。
- 第 $2$ 行到第 $M+1$ 行：每行三个整数 $A[i], B[i], T[i]$，表示一条现有的小路：
- 小路连接水坑 $A[i]$ 和水坑 $B[i]$；
- 通过这条小路需要 $T[i]$ 天。
水坑编号为 $0 \sim N-1$。
原图中任意两点之间至多存在一条简单路径（即原图是一个森林）。
输出格式
输出一个整数，表示在合理修建 $N-M-1$ 条新小路之后，从任意一个水坑到另一个水坑的最短路时间中的**最大值**（也就是最终图的最小可能直径）。
输入输出样例
输入 #1
12 8 2 0 8 4 8 2 2 2 7 4 5 11 3 5 1 7 1 3 1 1 9 5 10 6 3
输出 #1
18
说明/提示
对这组数据的一种最优修路方式是新修三条小路：
- 在水坑 $1$ 和 $2$ 之间；
- 在水坑 $1$ 和 $6$ 之间；
- 在水坑 $4$ 和 $10$ 之间。
新修完成后，所有水坑之间连通，从水坑 $0$ 到水坑 $11$ 的最短路径长度为 $18$ 天，是所有点对之间最短路中最大的值。可以证明这是最优答案。
## 数据范围
- $1 \le N \le 10^5$；
- $0 \le M \le N-1$；
- $0 \le A[i], B[i] \le N-1$；
- $1 \le T[i] \le 10^4$；
- $1 \le L \le 10^4$。
- 在水坑 $1$ 和 $2$ 之间；
- 在水坑 $1$ 和 $6$ 之间；
- 在水坑 $4$ 和 $10$ 之间。
新修完成后，所有水坑之间连通，从水坑 $0$ 到水坑 $11$ 的最短路径长度为 $18$ 天，是所有点对之间最短路中最大的值。可以证明这是最优答案。
## 数据范围
- $1 \le N \le 10^5$；
- $0 \le M \le N-1$；
- $0 \le A[i], B[i] \le N-1$；
- $1 \le T[i] \le 10^4$；
- $1 \le L \le 10^4$。