A5809. 「NOI2013」快餐店
编程题
省选/NOI-
知识点
题目描述
小 T 打算在城市 C 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，小 T 希望快餐店的地址选在离最远的顾客距离最近的地方。
快餐店的顾客分布在城市 C 的 $N$ 个建筑中，这 $N$ 个建筑通过恰好 $N$ 条双向道路连接起来，不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小 T 的快餐店可以开设在任一建筑中，也可以开设在任意一条道路的某个位置上（该位置与道路两端的建筑的距离不一定是整数）。
现给定城市 C 的地图（道路分布及其长度），请找出最佳的快餐店选址，输出其与最远的顾客之间的距离。
快餐店的顾客分布在城市 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$ 。
接下来 $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
输入 #2
5 1 5 100 2 1 77 3 2 80 4 1 64 5 3 41
输出 #2
109.0
说明/提示
对于 $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$。
对于 $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$。