← 返回题目
题库练习 「CTSC2017」网络
← 上一题 下一题 →

A6824 | 「CTSC2017」网络

时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

一个一般的网络系统可以被描述成一张无向连通图。图上每个节点为一个服务器，连接服务器与服务器的数据线则看作图上的一条边，边权为该数据线的长度。两个服务器之间的通讯距离定义为其对应节点之间的最短路长度。

现在，考虑一个当前图结构为树的网络系统。你作为该网络系统的管理员，被要求在这个系统中加入一条给定长度的数据线。数据线可以连在任意两个服务器上。

你的任务是，求出在所有合法的方案中，通讯距离最远的两个服务器之间的最小距离。

输入格式

输入包含多组数据。对于每组数据，输入的第一行包含两个正整数 $ n, L $，其中 $ n $ 表示服务器个数，$ L $ 为新加入的数据线的长度。
接下来 $ n - 1 $ 行，第 $ i $ 行有三个正整数 $ a_i, b_i, l_i $，表示有一条长度为 $ l_i $ 的数据线连接服务器 $ a_i, b_i $。服务器编号为 $ 1 \sim n $。
输入的末尾以两个 $ 0 $ 作为结束。

输出格式

对于每组数据，输出一行一个整数，描述在所有合法的方案中，通讯距离最远的两个服务器之间的最小距离。

输入输出样例

输入 #1
7 1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
0 0
输出 #1
3
输入 #2
6 26
1 2 66
2 3 11
3 4 73
2 5 77
3 6 33
10 47
1 2 86
2 3 69
3 4 41
4 5 26
5 6 41
2 7 73
3 8 77
4 9 2
5 10 65
0 0
输出 #2
143
232
C++ 编辑器
输入
输出