MST - Minimum Spanning Tree
Find the minimum spanning tree of the graph.
On the first line there will be two integers N - the number of nodes and M - the number of edges. (1 <= N <= 10000), (1 <= M <= 100000)
M lines follow with three integers i j k on each line representing an edge between node i and j with weight k. The IDs of the nodes are between 1 and n inclusive. The weight of each edge will be <= 1000000.
Single number representing the total weight of the minimum spanning tree on this graph. There will be only one possible MST.
Input: 4 5 1 2 10 2 3 15 1 3 5 4 2 2 4 3 40 Output: 17
|Added by:||Nikola P Borisov|
|Cluster:||Cube (Intel Pentium G860 3GHz)|
|Languages:||All except: ERL JS NODEJS PERL 6 VB.net|
hoc sinh test:
Problem for kids :DLast edit: 2015-07-23 17:17:08
dễ vãi :D
if we get 18.18 is it correct or not
Edit: Do not pick the first element from a vector and resize it again and again. This will case TLE as removing an element from the start of a vector causes it to resize taking O(n) time. Instead sort it in descending order nad keep poping the elements from the back which take O(1) time. I managed to get 100Last edit: 2015-05-26 09:26:07
Hey @Bharghav !!! How do we see your code?
even after using long long , i am getting 81.82.Can somebody please help
i am getting a compilation error although my code runs fine in ideone!..plz help
@paci :fair enough!!!
Antony Skarlatos (Hepic):
Use long long for distance(or weight),to take 100%.