A270.Gold King的大本营

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

Gold King家的农场分布在青青草原的多处地方,并且已经初具规模。在经过数据统计之后,需要定一个农场为大本营。

Gold King家有P(1P30,000)P(1 \le P \le 30,000)个农场,农场编号为1..P1..P,有C(1C100,000)C(1 \le C \le 100,000)条双向路径连接农场,路径编号为1..C1..C,每条路径ii连接农场aia_i和$b_i $(1aiP;1biP1 \le a_i\le P;1 \le b_i \le P),因为数据比较粗糙,路径可能连接aia_i到它自己,或者两个农场间有多条路径,距离为LiL_i。其中有KK个农场,编号为a1,a2,...,aka_1,a_2,...,a_k,规模庞大,为了方便管理,大本营得尽量离它们近一些,但是得从剩下的PKP-K个农场中候选,不能占用KK个农场的资源,问大本营到其中一个的KK个农场距离最近为多少。

输入格式

第一行输入包含三个整数PCKP、C、K,(1P,C105,0KP1\le P,C\le 10^5, 0\le K\le P) 分别表示Gold King的PP个农场、它们之间的道路数量CC和规模较为庞大的农场数量KK

接下来输入CC行,每行包含三个整数aia_ibib_iLiL_i,(1ai1\le a_i,biPb_i\le P,1Li1091\le L_i\le 10^9,ai=bia_i≠=b_i),表示aia_i农场到bib_i农场有一条长为LL的道路。
如果K>0K>0,则输入的最后一行包含kk个不同的整数a1a_1,a2a_2,......,aka_k(1ai1\le a_i\le  P),表示规模较大的农场编号。如果K=0),表示规模较大的农场编号。如果K=0则此行不会出现在输入中。

输出格式

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

输入输出样例

  • 输入#1

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

    输出#1

    3
首页