|Online Judge||Problem Set||Authors||Online Contests||User|
How Many Pairs?
You are given an undirected graph G with N vertices and M edges. Each edge has a length. Below are two definitions.
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.
The first line of input contains three integer N, M and Q (1 < N ≤ 10,000, 0 < M ≤ 50,000, 0 < Q ≤ 10,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 < 108) 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 < 108).
Output the answer to each query on a separate line.
4 5 4 1 2 1 2 3 2 2 3 5 3 4 3 4 1 4 0 1 3 2
0 1 6 3
POJ Monthly--2006.05.28, zhucheng
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator