威尼斯旅行

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file tripa.in Output file tripa.out

【题目描述】


毕业了,Xth很高兴,因为他要和他的rabbit去双人旅行了。他们来到了水城威尼斯。众所周知(⊙﹏⊙b汗),这里的水路交通很发达,所以xth和rabbit只好坐船穿梭于各个景点之间。但是要知道,rabbit是会晕船的,看到她难受,xth是会心疼的。

已知城市中有n个景点,这些景点之间有m条双向水路,在每条水路上航行时rabbit都会有一个"晕船值"。旅行时,xth会带着rabbit尽量选择晕船值小的路线旅行。但是rabbit也是有一定忍耐限度度的,如果晕船值超过了她的忍耐度,xth会果断决定放弃这条路线。

现在xth想进行若干次询问,给定rabbit的忍耐度,问还有多少对城市(x,y)间会存在可行的旅行路线(如果(x,z)和(z,y)可行,则(x,y)可行,也就是说连通性是可传递的)。



【输入格式】


第1行三个正整数n,m,q,分别表示景点数量、水路数量和询问次数。

第2行到第m+1行每行三个正整数x,y,w,表示x号景点和y号景点之间有一条"晕船值"为w的双向水路。

第m+2行至第m+q+1行,每行一个正整数k,表示询问中给定的rabbi忍耐度为k。



【输出格式】

共q行,对于每次询问做出回答。

【样例输入】

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

【样例输出】

4
10 

【提示】

第一个询问:(1,2),(1,5),(2,5),(3,4)。其中(2,5)的具体走法为:2−1−5 第二个询问:(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)。其中(4,5)的具体走法为:4−3−2−1−5

【数据规模】

对于20%的数据满足n≤20,m≤40,q≤40; 对于40%的数据满足n≤1000,m≤2000,q≤1000; 对于60%的数据满足n≤3000,m≤6000,q≤200000; 对于100%的数据满足n≤100000,m≤200000,q≤200000。其他数不超过10^9。

【细节提示】

1 给出的n个景点不一定全部互相连通,且两个景点之间可能存在多条道路,也可能存在某条边是从某景点出发回到他自己。

2 对于询问的结果可能很大,请注意使用适当的类型存储。