/ Vijos / 题库 /

行程

行程

时间限制: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

信息

ID
2246
难度
(无)
分类
搜索 | 枚举图结构 | 最短路 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
3
上传者