All Tracks Algorithms Graphs Articulation Points and Bridges Problem

Nick and JosephLand
Tag(s):

Data Structures, Medium-Hard, Trees

Problem
Editorial
Analytics

Nick is the mayor of JosephLand. He wants to make a reform of the roads in JosephLand. In JosephLand, there are $$n$$ cities, numbered 1 through $$n$$. There are also $$m$$ weighted, directed roads represented by three numbers:

  • $$u_i$$ $$v_i$$ $$w_i$$ : there is a road from $$u_i$$ to $$v_i$$ and the $$fine$$ taken on this road is $$w_i$$. That means, if you pass a road from $$v_i$$ to $$u_i$$, i.e violating the traffic law you have to pay $$w_i$$ coins, otherwise you don't have to pay anything.

Nick is going to have a travel. Travel consists of $$q$$ journeys. Each journey is represented by two numbers: $$a_i, b_i$$. That means, he starts his journey in $$a_i$$ and ends in $$b_i$$. Every time he will choose a journey with minimum $$cost$$. $$Cost$$ of a journey is equal to the sum of $$fines$$ he paid during the journey.

$$Consumption$$ of a travel is $$\sum_{j=1}^{q} cost_j$$. As Nick is the mayor of JosephLand, before the travel he can change directions of any roads as many times as he wants. So now Nick wants to change directions of some roads in such a way, that $$consumption$$ is minimal. Note that no changes can be made.

Input format

The first line contains two integers $$n$$, $$m$$ — the number of cities and the number of roads, respectively.

Next $$m$$ lines contain three integers each, $$u_i$$, $$v_i$$ and $$w_i$$ denoting there is a road from $$u_i$$ to $$v_i$$ and the $$fine$$ is $$w_i$$. Note that between a pair of cities can exist more than one road.

Next line contains a single integer $$q$$ — the number of journeys.

Next $$q$$ lines contain two integers each, $$a_i$$ and $$b_i$$ — the start and the end of the journey, respectively. Note that the start and the end can be the same city.

It is guaranteed that the JosephLand is connected.

Note: there can be a problem with stack size.

Output format

Print the minimum $$consumption$$ that Nick can achieve.

Constraints

  • $$1≤n, m, q≤5*10^5$$
  • $$1≤u_i, v_i≤n; u_i≠v_i$$
  • $$1≤w_i≤10^6$$
  • $$1≤a_i, b_i≤n$$

Subtasks

  • Subtask #1 (10 points) : $$1≤n, m, q≤10$$
  • Subtask #2 (90 points) : Original constraints
SAMPLE INPUT
7 7
4 6 7
4 5 10
5 7 3
3 5 3
1 2 5
7 3 6
2 6 1
2
6 5
7 4
SAMPLE OUTPUT
10
Explanation

We can change directions of first and third roads. The graph will be as follows:enter image description here

From 6 to 5 there is only path and we don't pay anything, so $$cost_1$$ = 0

From 7 to 5 we have to pay $$fine$$ for passing the road from 5 to 4, so $$cost_2$$ = 10

Overall $$consumption$$ =10 and you can not achieve better than this answer!

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications