问题 25411 --Ali的宝藏

25411: Ali的宝藏

时间限制: 1 Sec  内存限制: 128 MB
提交: 76  解决: 18
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][604kb]

题目描述

阿狸是很财迷的!他喜欢收集宝藏。
阿狸秘密的了解到花园里面藏有P 个宝藏。经过严密调查, 他知道花园分成了N块区域,由M 条无向路径连接。
阿狸要从1 区域出发,捡完所有的宝藏后从N区域离开。阿狸被发财的白日梦冲昏了头脑,没有办法冷静下来想想挖宝的对策,于是鸡冻的他找你帮忙:最短走多远就能捡完宝藏并离开?

输入

第1行两个整数M,N。
第2行到第M +1 行, 每行三个整数x 、y 、w,表示x、y号区域(1≤x、y≤N)间有一条道路,该道路长度为w。 
第M +2行一个整数P。
第M +3 行有用空格隔开的P 个整数,第i 个数Pi 代表第i 个珍品藏在第Pi 个区域。

输出

第1 行为一个整数,为阿狸拿到所有宝藏并离开的所需走过的最短道路长度。 如无法全部捡到或者无法离开,输出-1 。

样例输入

2 3
1 2 3
2 3 4
1
2

样例输出

7

提示

【样例说明】

直接按1->2->3 路线走, 可以拿走2 区域的宝藏, 并以最短时间7 到达3 区域(即N号区域)。

【数据范围】

对30%的数据,1≤N≤10 ,1≤M≤100,0≤P≤5 。

对100%的数据,1≤N≤200,1≤M≤10,000,0≤P≤12,道路长度不超过1,000,000,000 。

其中,N 、M 、P 、道路长度均为整数。

来源

[提交][状态]