A New Country

View as PDF
Submit solution
Points: 25 (partial)
Time limit: 1.8s
Memory limit: 512M
Author:
Ninjaclasher
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 need 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 \ne 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 \ne 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.

Constraints

Subtask 1 [8%]

Q \le 100

Subtask 2 [16%]

p_i = 1

Subtask 3 [16%]

d_i = 1

Subtask 4 [60%]

No additional constraints.

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
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation.

Comments


  • 5
    loltrollkill  commented on Nov. 30, 2018, 11:46 p.m.

    RIP evening.


  • 5
    KevinWan  commented on April 19, 2018, 4:15 a.m.

    Is the distance we have to find, the minimum possible distance?