A6283 | $Welcome24ever 和水坑$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

天地之初，IOI 还只是遥远的梦想。 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-1$ 条新小路之后，从任意一个水坑到另一个水坑的最短路时间中的 最大值 （也就是最终图的最小可能直径）。

输入 #1

输出 #1

C++ 编辑器

输入

输出