Problem 1054 --E.集合近点

1054: E.集合近点

Time Limit: 6 Sec  Memory Limit: 512 MB
Submit: 242  Solved: 21
[Submit][Status][Web Board][Creator:]

Description

给出一个n个顶点m条边的无向图,每条边有非负权值。

现在Alice在这个图上标记了一些自己喜欢的点,我们假设这些Alice喜欢的点为一个集合。Alice认为,集合外的所有点中,如果某个点是可以从集合内的某个点出发,最多走不超过距离p就可以到达的,那么该点就认为是集合近点。Alice想知道对于给定的图和集合,有多少近点。笨笨的Alice当然不会这个问题,然后又马上跑去问Bob了。Bob很忙,然后就交了你,希望你能写个程序解决该问题。

注意:给定的图不保证没有重边和自环,给定的集合不保证没有重复的点

Input

输入第一行包含四个正整数n(2<=n<=100000),m(1<=m<=200000),p(1<=p<=1e9)和k(1<=k<n),表示顶点数、边的数目、最大走的距离以及集合点数。

接下来一行,包含k个整数。第i个整数ai,表示顶点ai是集合的点。

接下来m行,每行3个整数。

第i行输入ui,vi(1<=ui,vi<=n),wi(0<=wi<=10000),表示顶点ui和vi之间存在一条权值为wi的无向边。

Output

对于每组输入,输出一行。输出一个整数表示满足要求的非集合的顶点数目。

Sample Input

5 5 3 2
1 5
1 2 3
2 3 1
3 4 5
1 4 2
4 5 3

Sample Output

2

HINT

集合是{1,5},4到{1,5}的最短距离是2,2到{1,5}的距离是3,这两个距离不大于p(p=3),但是3到{1,5}的最短距离是4>p,不符合,所以答案是2

Source

[Submit][Status]