[Solution] Ela and the Wiring Wizard solution codeforces

Ela and the Wiring Wizard solution codeforces – Ela needs to send a large package from machine 11 to machine 𝑛n through a network of machines. Currently, with the network condition, she complains that the network is too slow and the package can’t arrive in time. Luckily, a Wiring Wizard offered her a helping hand.

Table of Contents

[Solution] Ela and the Wiring Wizard solution codeforces

The network can be represented as an undirected connected graph with 𝑛n nodes, each node representing a machine. 𝑚m wires are used to connect them. Wire 𝑖i is used to connect machines 𝑢𝑖ui and 𝑣𝑖vi, and has a weight 𝑤𝑖wi. The aforementioned large package, if going through wire 𝑖i, will move from machine 𝑢𝑖ui to machine 𝑣𝑖vi (or vice versa) in exactly 𝑤𝑖wi microseconds. The Wiring Wizard can use his spell an arbitrary number of times. For each spell, he will choose the wire of index 𝑖i, connecting machine 𝑢𝑖ui and 𝑣𝑖vi, and rewire it following these steps:

  • Choose one machine that is connected by this wire. Without loss of generality, let’s choose 𝑣𝑖vi.
  • Choose a machine that is currently connecting to 𝑣𝑖vi (including 𝑢𝑖ui), call it 𝑡𝑖ti. Disconnect the wire indexed 𝑖i from 𝑣𝑖vi, then using it to connect 𝑢𝑖ui and 𝑡𝑖ti.

The rewiring of wire 𝑖i will takes 𝑤𝑖wi microseconds, and the weight of the wire will not change after this operation. After a rewiring, a machine might have some wire connect it with itself. Also, the Wiring Wizard has warned Ela that rewiring might cause temporary disconnections between some machines, but Ela just ignores it anyway. Her mission is to send the large package from machine 11 to machine 𝑛n as fast as possible. Note that the Wizard can use his spell on a wire zero, one, or many times. To make sure the network works seamlessly while transferring the large package, once the package starts transferring from machine 11, the Wiring Wizard cannot use his spell to move wires around anymore.

Ela wonders, with the help of the Wiring Wizard, what is the least amount of time needed to transfer the large package from machine 11 to 𝑛n.

[Solution] Ela and the Wiring Wizard solution codeforces

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡1001≤t≤100). The description of the test cases follows.

The first line contains 𝑛n and 𝑚m (2𝑛5002≤n≤500𝑛1𝑚250000n−1≤m≤250000), the number of nodes and number of wires, respectively.

For the next 𝑚m lines, 𝑖i-th line will contains 𝑢𝑖ui𝑣𝑖vi and 𝑤𝑖wi (1𝑢𝑖,𝑣𝑖𝑛1≤ui,vi≤n1𝑤𝑖1091≤wi≤109) – the indices 2 machines that are connected by the 𝑖i-th edge and the weight of it.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 500500 and the sum of 𝑚m over all test cases does not exceed 250000250000. The graph in each test case is guaranteed to be connected, no self-loops, but it can contain multiple edges.

Output

For each test case, output one integer denotes the least amount of time needed to transfer the large package from machine 11 to 𝑛n.

[Solution] Ela and the Wiring Wizard solution codeforces

input

Copy
3
8 9
1 2 3
6 4 5
3 5 6
6 1 3
7 4 4
3 8 4
2 3 3
7 8 5
4 5 2
4 5
1 2 1
2 4 1
3 4 1
3 1 1
1 3 2
8 8
4 6 92
7 1 65
6 5 43
6 7 96
4 3 74
4 8 54
7 4 99
2 5 22
output

Copy
9
2
154

[Solution] Ela and the Wiring Wizard solution codeforces

Here is the graph in the first test case in the sample input:

Ela can ask the Wiring Wizard to use his spell on wire with the index of 77, which is connecting machines 22 and 33. Then, since the machine 88 is connected to machine 33, the Wiring Wizard can disconnect wire 77 from machine 33 and connect it to wire 88 in 33 microseconds (weight of wire 33).

After that, the package can be sent from machine 11 to machine 88 in 66 microseconds. Therefore, the answer is 3+6=93+6=9 microseconds.

Here is the graph in the third test case in the sample input:

For Solution

“Click Here”

Leave a Comment