行程
时间限制:1秒 内存限制:256M
【题目描述】
小H经过一段紧张信息学竞赛的训练后,决定要放松一下去 \(C\) 地,于是他搞来一张地图,看怎么走好。
地图上有很多城市,\(C\) 地也是一座城市。每两座城市之间可能有直达方法,也可能两座城市之间并不能直接相通,而要通过其他城市转达。对于两个城市之间的直达方法,需要一定的时间,如果从城市 \(A\) 到城市 \(B\) 的直达方法需要 \(T\) 时间,那么从 \(B\) 城市到 \(A\) 城市的直达方法也是 \(T\) 时间。
小H想用最短的时间到达 \(C\) 地,但是有个问题,他发现,地图上有些城市对他很有吸引力。所以他要经过这些城市的基础上时间最短。
小H已经用 \(1,2,…,n\) 标记了他可能经过的城市(1 代表出发地,\(n\) 代表 \(C\) 地),但眼花缭乱的地图让他感到烦劳。他请你来解决这个问题,告诉他最少需要多少时间到达 \(C\) 地。
【输入格式】
第一行是三个整数 \(n\) 和 \(m,t\),其中 \(n\) 代表城市数目,\(m\) 代表直达路线,\(t\) 代表一定要去的城市数目(不包含出发地和 \(C\) 地)。
接下来一行有 \(t\) 个整数,表示一定要去的城市。
再接下来 \(m\) 行,每行包含三个整数,前两个整数分别表示一个城市,第三个整数是这两座城市之间直达时间。直达时间不会超过 1000000。
【输出格式】
输出一个整数,符合题目要求的最短时间。
【输入输出样例】
Input
5 10 2
2 3
1 2 5
1 3 45
1 4 61
1 5 81
2 3 9
2 4 91
2 5 4
3 4 74
3 5 42
4 5 61
Output
27
【数据限制】
对于 \(100\%\) 的数据,\(1≤n≤200\),\(1≤m≤20000\),\(1≤t≤10\)。
【来源】
Mr.he