Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Wakanda Forever

By aaman007 · Limits 1s, 512 MB

We all know that Thanos has erased half of the population of the universe. Earth’s population was also decreased from 7 billion to 3.5 billion.

In Wakanda there are n cities (numbered 1 to n ) connected by m bidirectional roads.

As T’Challa was disintegrated by the Thanos snap, M’Baku is the new king of Wakanda. M’Baku wants to close some of the roads of Wakanda because the population of some cities were erased completely and some roads are unnecessary.

As you are M’Baku‘s friend , he asked you to help him to minimize the number of roads necessary so that all cities with people are connected and the total length of all active roads will be minimized.

Note that, it is possible that by closing some roads, Wakanda may not be connected anymore. In that case, M’Baku will need to create some new roads each having length d.

If a city doesn’t have any people left on it, all roads connected to it should be closed.


The first line of the input contains three integers, n , m and d (2 ≤ n ≤ 105 , n-1 ≤ m ≤ 3 * 105 , 1 ≤ d ≤ 100), the number of cities currently in Wakanda , the number of roads and the lengths of new roads.

The second line contains n integers, denoting number of people a[i] (0 ≤ a[i] ≤ 100) in city i after the disintegration .

The next m lines each contain three integers, u , v and w (1 ≤ u,v ≤ n , 1 ≤ w ≤ 100), the road end-points and lengths.


Print the total length of all active roads after you help M’Baku.


5 6 100
100 100 5 0 10
1 2 3
1 4 1
1 3 3
3 4 1
2 4 5
4 5 1



85% Solution Ratio

prodip_bsmrstuEarliest, Apr '19

Sourav_1704093Fastest, 0.1s

riyad000Lightest, 3.9 MB

zishan044Shortest, 913B


Login to submit


It was a minimum spanning tree problem. For Wakanda to be connected it needs (number of cities that...