A New Country

View as PDF

Submit solution

All submissions

Best submissions

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$ $N$ cities connected by $M$ $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$ $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$ $P - 1$ roads connecting the $P$ $P$ provinces. These $P-1$ $P - 1$ roads are included in the initial $M$ $M$ roads. Furthermore, he has guaranteed that all provinces are connected, that is, each province has either an indegree greater than $0$ $0$ , an outdegree greater than $0$ $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$ $a$ and city $b$ $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$ $Q$ times.

Input Specification

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

The next $M$ $M$ lines will each contain three space-separated integers, $a_i\ b_i\ d_i$ $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)$ $(1 \leq a_{i}, b_{i} \leq N, a_{i} \neq b_{i}, 1 \leq d_{i} \leq 10^{5})$ , indicating that there is a road connecting city $a_i$ $a_{i}$ and city $b_i$ $b_{i}$ of length $d_i$ $d_{i}$ .

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

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

Constraints

Subtask 1 [8%]

$Q \le 100$ $Q \leq 100$

Subtask 2 [16%]

$p_i = 1$ $p_{i} = 1$

Subtask 3 [16%]

$d_i = 1$ $d_{i} = 1$

Subtask 4 [60%]

No additional constraints.

Output Specification

For each query, output the minimum distance from $a_i$ $a_{i}$ to $b_i$ $b_{i}$ on a new line for Evan.

Sample Input 1

Copy

Sample Output 1

Copy

Sample Input 2

Copy

Sample Output 2

Copy

Sample Input 3

Copy

Sample Output 3

Copy

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?

5

wleung_bvg commented on April 19, 2018, 5:23 a.m.

Yes