A270.Gold King的大本营
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
Gold King家的农场分布在青青草原的多处地方,并且已经初具规模。在经过数据统计之后,需要定一个农场为大本营。
Gold King家有P(1≤P≤30,000)个农场,农场编号为1..P,有C(1≤C≤100,000)条双向路径连接农场,路径编号为1..C,每条路径i连接农场ai和$b_i $(1≤ai≤P;1≤bi≤P),因为数据比较粗糙,路径可能连接ai到它自己,或者两个农场间有多条路径,距离为Li。其中有K个农场,编号为a1,a2,...,ak,规模庞大,为了方便管理,大本营得尽量离它们近一些,但是得从剩下的P−K个农场中候选,不能占用K个农场的资源,问大本营到其中一个的K个农场距离最近为多少。
输入格式
第一行输入包含三个整数P、C、K,(1≤P,C≤105,0≤K≤P) 分别表示Gold King的P个农场、它们之间的道路数量C和规模较为庞大的农场数量K。
接下来输入C行,每行包含三个整数ai、bi、Li,(1≤ai,bi≤P,1≤Li≤109,ai==bi),表示ai农场到bi农场有一条长为L的道路。
如果K>0,则输入的最后一行包含k个不同的整数a1,a2,...,ak(1≤ai≤ P),表示规模较大的农场编号。如果K=0则此行不会出现在输入中。
输出格式
输出一个整数,表示大本营到达其中K个农场最近距离为多少。若无法设立大本营,输出−1。)
输入输出样例
输入#1
5 4 2 1 2 5 1 2 3 2 3 4 1 4 10 1 5
输出#1
3