oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

newroads Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

newroads.html

Problem Description

Potatoland has N cities, and E roads connecting those cities, and it is guaranteed that it is possible to travel between any pair of cities in Potatoland with these roads. Each road i connects cities Ai and Bi, and has a length of Li. The distance between any pair of cities is defined as the sum of lengths of the roads in the shortest path between the two cities, and the connectivity value of Potatoland is defined as the sum of distances between any two cities.

The mayor of Potatoland is planning to build a total of R new roads, in a particular order. The ith road that is built will connect cities Si and Ti with a road of length Wi. After the construction of each road, output the connectivity value of Potatoland.

Input

The first line of input will contain three integers, N, E and R.

The next E lines of input will contain three integers each, Ai, Bi and Li.

The next R lines of input will contain three integers each, Si, Ti and Wi.

Output

The output should contain R lines with one integer each, with the ith line containing the connectivity value of Potatoland after the construction of the ith road.

Limits

For all subtasks: 1 ≤ Li, Wi ≤ 109, 0 ≤ Ai, Bi, Si, Ti < N.

Subtask 1 (29%): 1 ≤ N ≤ 70, N - 1 ≤ E ≤ 2500, 1 ≤ R ≤ 100.

Subtask 2 (20%): 1 ≤ N ≤ 300, N - 1 ≤ E ≤ 45000, R = 1.

Subtask 3 (51%): 1 ≤ N ≤ 300, N - 1 ≤ E ≤ 45000, 1 ≤ R ≤ 300.

Subtask 4 (0%): Sample Testcases.

Sample Input 1

4 3 1
0 1 3
1 2 3
2 3 3
3 0 3

Sample Output 1

24

Sample Input 2

5 5 3
0 3 4
3 4 1
3 2 5
4 1 3
1 2 1
3 1 2
2 1 6
0 4 1

Sample Output 2

36
36
26

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
129211s256MBMinimum
220211s256MBMinimum
351621s256MBMinimum
4021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o newroads -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.