a073:
POJ2832 How Many Pairs?

Content

You are given an undirected graph *G* with *N* vertices and *M* edges. Each edge has a length. Below are two definitions.

- Define
*max_len*(*p*) as the length of the edge with the maximum length of*p*where*p*is an arbitrary non-empty path in*G*. - Define
*min_pair*(*u*,*v*) as min{*max_len*(*p*) |*p*is a path connecting the vertices*u*and*v*.}. If there is no paths connecting*u*and*v*,*min_pair*(*u*,*v*) is defined as infinity.

Your task is to count the number of (unordered) pairs of vertices *u* and *v* satisfying the condition that *min_pair*(*u*, *v*) is not greater than a given integer *A*.

Input

The first line of input contains three integer *N*, *M* and *Q* (1 < *N* ≤ 100,000, 0 < *M* ≤ 200,000, 0 < *Q* ≤ 200,000). *N* is the number of vertices, *M* is the number of edges and *Q* is the number of queries. Each of the next *M* lines contains three integers *a*, *b*, and *c* (1 ≤ *a*, *b* ≤ *N*, 0 ≤ *c* < 10^{8}) describing an edge connecting the vertices *a* and *b* with length *c*. Each of the following *Q* lines gives a query consisting of *a* single integer *A* (0 ≤ *A* < 10^{8}).

Output

Output the answer to each query on a separate line.

Sample Input
#1

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

Sample Output
#1

0 1 6 3

測資資訊：

記憶體限制：
512
MB

公開 測資點#0 (100%): 3.0s , <10M

公開 測資點#0 (100%): 3.0s , <10M

原题范围是

1 < *N* ≤ 10,000, 0 < *M* ≤ 50,000, 0 < *Q* ≤ 10,000

这里改为

1 < *N* ≤ 100,000, 0 < *M* ≤ 200,000, 0 < *Q* ≤ 200,000

为了不让O(N^2)的过...

POJ 2832

这里，N个点的编号是1,2,3,4,5,....,N

ID | User | Problem | Subject | Hit | Post Date |

沒有發現任何「解題報告」 |