#2669. 「NOI2013」快餐店

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 T 打算在城市 C 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的,小 T 希望快餐店的地址选在离最远的顾客距离最近的地方。

快餐店的顾客分布在城市 C 的 N 个建筑中,这 N 个建筑通过恰好 N 条双向道路连接起来,不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小 T 的快餐店可以开设在任一建筑中,也可以开设在任意一条道路的某个位置上(该位置与道路两端的建筑的距离不一定是整数)。

现给定城市 C 的地图(道路分布及其长度),请找出最佳的快餐店选址,输出其与最远的顾客之间的距离。

输入格式

第一行包含一个整数 N ,表示城市 C 中的建筑和道路数目。

接下来 N 行,每行 3 个整数 A_i B_i L_i 1 \le i \le N; L_i > 0 ),表明一条道路连接了建筑 A_i B_i ,其长度为 L_i

输出格式

输出一个实数,四舍五入保留恰好一位小数,表示最佳快餐店选址距离最远用户的距离。

注意:你的结果必须恰好有一位小数,小数位数不正确不得分。

样例

样例输入 1

4
1 2 1
1 4 2
1 3 2
2 4 1

样例输出 1

2.0

样例解释 1

如图所示,最优选址为建筑 1 。到达 4 个建筑的距离分别为 0,1,2,2

样例输入 2

5
1 5 100
2 1 77
3 2 80
4 1 64
5 3 41

样例输出 2

109.0

样例解释 2

样例输入输出 3

见附加文件中的 foodshop.infoodshop.ans.

数据范围与提示

对于 10\% 的数据, N \le 80 L_i = 1

对于 30\% 的数据, N \le 600 L_i \le 100

对于 60\% 的数据, N \le 2000 L_i \le 10^9

对于 100\% 的数据, N \le 10^5 L_i \le 10^9