A New Country

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 4.0s
Memory limit: 512M

Author:
Problem types

Evan is planning a new country. In his ideal country, there are N cities connected by M weighted directed roads. The weight of each road is the distance between the two cities it is connecting. These cities are grouped into P provinces. A province, according to Evan, is a maximal group of cities such that every city is able to visit every other city in that province.

Evan wants to keep the provinces as segregated as possible for reasons we dare not know about. As such, he has decided that there will only be P-1 roads connecting the P provinces. These P-1 roads are included in the initial M roads. Furthermore, he has guaranteed that all provinces are connected, that is, each province has either an indegree greater than 0, an outdegree greater than 0, or both. In other words, the provinces form a tree.

Soon after, Evan is told that with his current plan, not every province can visit every other province. Realizing his mistake, he has decided that all roads between any two provinces will be upgraded to be bidirectional. The distance between city a and city b in both directions, however, will be the same.

With the country's roads planned out, Evan wants you to find the distance between two cities so that he can decide if any other roads needs to be built. He will ask you Q times.

Input Specification

The first line will contain three space-separated integers, N (1 \le N \le 10^4), M (1 \le M \le 10^5), Q (1 \le Q \le 10^5), the number of cities, roads, and queries respectively.

The next M lines will each contain three space-separated integers, a_i b_i d_i (1 \le a_i,b_i \le N,a_i \neq b_i, 1 \le d_i \le 10^5) indicating that there is a road connecting city a_i and city b_i of length d_i.

The next Q lines will each contain two space-separated integers, a_i b_i (1 \le a_i, b_i \le N, a_i \neq b_i), indicating that Evan would like to know the distance from city a_i to city b_i.

It is guaranteed that 1 \le P \le 10^3, and p_i \le 200. That is, the number of provinces is less than or equal to 10^3 and the number of cities in each province is less than or equal to 200.

Subtasks

For 2 of the 25 available marks, Q \le 100.

For an additional 4 of the 25 available marks, p_i = 1.

For an additional 4 of the 25 available marks, d_i = 1.

Output Specification

For each query, output the minimum distance from a_i to b_i on a new line for Evan.

Sample Input 1

10 13 5
1 2 3
2 3 2
3 1 10
4 1 5
3 4 7
10 3 2
6 10 1
6 7 8
5 7 7
5 6 4
7 8 6
8 9 9
9 5 1
1 8
3 1
9 10
5 2
4 6

Sample Output 1

22
10
6
20
13

Sample Input 2

9 12 4
1 2 1
2 1 1
1 3 1
3 4 1
4 3 1
2 5 1
5 6 1
6 5 1
6 7 1
6 8 1
8 9 1
9 8 1
1 9
7 4
2 8
6 3

Sample Output 2

5
6
3
4

Sample Input 3

14 19 7
1 2 1
2 3 5
3 1 3
2 4 2
4 5 4
5 4 1
4 10 8
10 11 10
11 12 5
12 11 6
4 6 3
6 7 1
7 8 3
8 9 2
9 6 1
8 6 4
7 13 2
13 14 5
14 13 1
1 8
13 12
5 9
11 3
7 4
2 14
10 6

Sample Output 3

10
34
10
25
9
13
11

Comments

There are no comments at the moment.