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 |

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