OI题库

【题目描述】

毕业了，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 对于询问的结果可能很大，请注意使用适当的类型存储。