最短路

path.cpp/in/out/1s/256M

【问题描述】

给定一个n个点m条边的有向图,有k个标记点,要求从规定的起点按任意顺序经过所有标记点到达规定的终点,问最短的距离是多少。

【输入描述】

第一行5个整数n、m、k、s、t,表示点个数、边条数、标记点个数、起点编号、终点编号。
接下来m行每行3个整数x、y、z,表示有一条从x到y的长为z的有向边。
接下来k行每行一个整数表示标记点编号。

【输出描述】

输出一个整数,表示最短距离,若没有方案可行输出-1

【样例】

path.in

3 3 2 1 1
1 2 1
2 3 1
3 1 1
2
3

path.out

3

【样例解释】

路径为1->2->3->1。

【数据范围】

20%的数据n<=10。
50%的数据n<=1000。
另有20%的数据k=0。
100%的数据n<=50000,m<=100000,0<=k<=10,1<=z<=5000。

信息

ID
1059
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者