#P9045. [2017年备战省选]最小直径
[2017年备战省选]最小直径
题目描述
给定一片有 个顶点和 条带权边的森林。你可以在已有顶点之间加入若干条边,每条新边的长度均为 。加入后必须得到一棵树。求最终树的直径最小可以是多少。
输入格式
第一行三个整数 。
接下来 行,每行三个整数 ,表示顶点 之间有一条长度为 的边。本站评测的顶点编号为 到 。
输出格式
输出一行一个整数,表示最小直径。
样例
12 8 2
1 9 4
9 3 2
3 8 4
6 12 3
6 2 7
2 4 1
2 10 5
11 7 3
18
数据范围
对于全部数据,,,。
原题给出的数据范围包括 的数据满足 , 的数据满足 。
原 PDF 的顶点编号从 开始。本站全部 10 组评测使用从 开始的编号,以上样例也将原编号各加了 ,直径答案保持为 。