A359 | $Gold King的大本营$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

Gold King家的农场分布在青青草原的多处地方，并且已经初具规模。在经过数据统计之后，需要定一个农场为大本营。 Gold King家有$P(1 \le P \le 30,000)$个农场，农场编号为$1..P$，有$C(1 \le C \le 100,000)$条双向路径连接农场，路径编号为$1..C$，每条路径$i$连接农场$a_i$和$b_i $($1 \le a_i\le P;1 \le b_i \le P$)，因为数据比较粗糙，路径可能连接$a_i$到它自己，或者两个农场间有多条路径，距离为$L_i$。其中有$K$个农场，编号为$a_1,a_2,...,a_k$，规模庞大，为了方便管理，大本营得尽量离它们近一些，但是得从剩下的$P-K$个农场中候选，不能占用$K$个农场的资源，问大本营到其中一个的$K$个农场距离最近为多少。

第一行输入包含三个整数$P、C、K$,($1\le P,C\le 10^5, 0\le K\le P$) 分别表示Gold King的$P$个农场、它们之间的道路数量$C$和规模较为庞大的农场数量$K$。 接下来输入$C$行，每行包含三个整数$a_i$、$b_i$、$L_i$，（$1\le a_i$,$b_i\le P$,$1\le L_i\le 10^9$,$a_i≠=b_i$），表示$a_i$农场到$b_i$农场有一条长为$L$的道路。 如果$K>0$，则输入的最后一行包含$k$个不同的整数$a_1$,$a_2$,$...$,$a_k$($1\le a_i\le$  P$)，表示规模较大的农场编号。如果K=0$则此行不会出现在输入中。

输出一个整数，表示大本营到达其中$K$个农场最近距离为多少。若无法设立大本营，输出$-1$。）

输入 #1

输出 #1

C++ 编辑器

输入

输出