问题1459--宝 物

1459: 宝 物

时间限制: 1 Sec  内存限制: 128 MB
提交: 17  解决: 7
[状态] [讨论版] [提交] [命题人:]
题目描述

传说HMH大沙漠中有一个迷宫,里面藏有许多宝物。迷宫里可能有N个藏宝地点,用1到N标记。藏宝地点之间最多有一条通路相连。标记1为迷宫的进出口。

某天,Dr.Kong找到了迷宫的地图,他已经知道其中K(1<=K<=N)个不同的地点真的藏有宝物。Dr.Kong决定让他的机器人卡多去探险。卡多在经过某个藏宝地点时可能会拿走宝物。但它每拿走一个藏宝地点的宝物后,它的载重量就会增加W。迷宫中的通路不是平坦的,到处都是陷阱。假设每条通路都有一个危险度,其值与通过此路的载重量成正比。

机器人卡多进入迷宫时,它的载重量为0。只有当卡多携带宝物的载重量不大于某个通路的危险度时,它才能顺利通过此条道路,否则就会掉入陷阱,不能出来。

Dr.Kong希望他的机器人卡多尽量多的带出宝物,当然他更希望卡多最后能从标记1的地点走出去。

请你编写程序,帮助Dr.Kong计算一下,卡多最多能带出多少个藏宝地点的宝物。

输入

第1行:         N M K W

接下来有K行,  每行一个整数,表示藏有宝物的地点标号。

再接下来有M行,每行三个整数X,Y,Z,表示地点X与地点Y之间有一条危险度为Z的通路。

输出

输出个整数 表示卡多最多能带出的宝物的堆数。

1 ≤ N ≤ 8000   1  K ≤ N    1 ≤ ≤ 15000  1 ≤ W, Z ≤ 10000

据保证所有的地点之间都是有道路可以到达的

提示:机器人卡多经过一个藏宝地点时可以不拿走宝物, 而且同一个藏宝地点可以经过多次。

样例输入 Copy
6 7 5 1
1
2
3
4
5
1 2 3
3 6 2
6 2 10
2 4 1
5 1 1
4 5 1
1 6 1
样例输出 Copy
4