← 返回题目列表

AtCoder · joi2011ho3

C. JOI王国购物

中文机器翻译题面 查看原题

配点: 100 点

在JOI国家 它们之间有 N 城镇。 M 它们由一条允许双向交通的道路连接。K 城镇有购物中心,市民可以通过公路前往其中一个城镇购物。

根据您家的位置,您可能需要长途跋涉才能去购物,这可能非常不方便。为了了解这种情况,国王决定根据房屋的位置找出到有购物中心的城镇的最短距离有多长。房屋有时建在道路中间(输入示例 请参阅 1 的解释 ),这个调查难度极大。因此,国王要求你这个优秀的程序员创建一个程序来进行调查。

課題

给定道路信息和购物中心所在城镇的信息,编写一个程序,求从购物中心所在城镇到道路上最远点(包括终点)的距离。您可以忽略在城镇内行驶的距离。

制限

2 \leqq N \leqq 3\,000  JOI国家城镇数量
1 \leqq M \leqq 100\,000\, (=10^5)  JOI 全国道路数量
1 \leqq K\leqq N  拥有购物中心的城镇数量
1 \leqq l_i \leqq 1\,000  i 道路长度

入力

从标准输入读取以下输入。

  • 1 行是一个整数 N, M, K 用空格分隔。N 是 JOI 国家/地区的城镇数量,M 是JOI国家的道路数量,K 代表拥有购物中心的城镇数量。在城里 编号为 1,2,\ldots,N 它正在被完成。
  • 继续 已组装的对在 M 线代表道路信息。i + 1 行目 (1\leqq i \leqq M) 是一个整数 a_i,b_i,l_i (1\leqq a_i\leqq N,1\leqq b_i\leqq N,1\leqq l_i\leqq 1000) 用空格分隔。这是i 主干道是镇 a_i 和镇 b_i 长度是 l_i 。道路的两端永远不会在同一个城镇。另外,任何 2 镇 对于 p, q , 连接p 和 按字典顺序比较 q 的道路 2 仅此而已。您可以沿着几条路从任何城镇前往任何其他城镇。
  • 继续 已组装的对在 K 行代表购物中心信息。i + M + 1 行目 (1 \leqq i \leqq K) 是 1 整数 s_i (1 \leqq s_i \leqq N)被写入。这是一个城镇 表示 s_i 有一个购物中心。 相同的值位于 s_1,\ldots, s_K 中 它出现的次数不能超过 2 次。

出力

标准输出是一个整数,它是到购物中心所在城镇的最短距离的最大值,四舍五入到最接近的整数。 1 输出一。

採点基準

评分数据中,分配的分数 40 对于%,K = 1 很满意。


入力例 1

3 3 1
1 2 1
2 3 1
3 1 1
1

出力例 1

2

入力例 1 代表以下城镇。路的长度都是 1 。购物中心就是城镇 仅适用于 1 。

距离购物中心所在城镇最远的点是城镇 连接 2 和镇 3 路上的一个小镇 距 2 的距离 该点位于 0.5 ,到购物中心所在城镇的距离为 1.5 。因此,它是四舍五入到最接近的整数的值。 输出 2 。


入力例 2

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

出力例 2

3