#P9045. [2017年备战省选]最小直径

    ID: 9251 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>CF2000提高无向连通分量两次遍历求直径深度优先搜索图构造

[2017年备战省选]最小直径

题目描述

给定一片有 nn 个顶点和 mm 条带权边的森林。你可以在已有顶点之间加入若干条边,每条新边的长度均为 LL。加入后必须得到一棵树。求最终树的直径最小可以是多少。

输入格式

第一行三个整数 n,m,Ln,m,L。

接下来 mm 行,每行三个整数 u,v,wu,v,w,表示顶点 u,vu,v 之间有一条长度为 ww 的边。本站评测的顶点编号为 11 到 nn。

输出格式

输出一行一个整数,表示最小直径。

样例

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

数据范围

对于全部数据,1≤n≤500001\le n\le50000,0≤m<n0\le m<n,1≤L,w≤10001\le L,w\le1000。

原题给出的数据范围包括 20%20\% 的数据满足 n≤5n\le5,60%60\% 的数据满足 n≤2000n\le2000。

原 PDF 的顶点编号从 00 开始。本站全部 10 组评测使用从 11 开始的编号,以上样例也将原编号各加了 11,直径答案保持为 1818。

原题面 PDF · 原题解 PDF