MST - Minimum Spanning Tree
Find the minimum spanning tree of the graph.
Input
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.
Output
Single number representing the total weight of the minimum spanning tree on this graph. There will be only one possible MST.
Example
Input: 4 5 1 2 10 2 3 15 1 3 5 4 2 2 4 3 40 Output: 17
hide comments
Avneet:
2013-06-12 10:18:48
my solution got accepted , but result is 0 , wht it means ? |
|
Lai Manh Tuan:
2013-01-10 10:55:14
@ Aman Gupta: Thanks for the suggestion |
|
Aman Gupta:
2012-10-08 17:52:24
Anyone getting exactly 81.82 as their score should use long long. Both Prim's (with heap) and Kruskal's pass in time. Last edit: 2012-10-09 11:20:42 |
|
Haidar Abboud:
2012-08-01 00:32:15
hope to see more textbook problems like this one -- useful to test the efficiency of your implementation |
|
Giorgos Christoglou:
2012-02-24 15:19:49
@ Nicolas i quess WA ... |
|
.::Manish Kumar::.:
2010-12-21 06:22:26
Last edit: 2012-03-30 11:48:26 |
|
যোবায়ের:
2010-06-16 18:44:48
A score of 100 means you have passed all the test data. In Partial problems, your score reflects the percentage of total correct answers your solution produced. |
|
Nicholas James:
2009-03-19 19:58:34
I looked at the best solutions and don't understand how to scoring is done for this problem. |
Added by: | Nikola P Borisov |
Date: | 2008-10-20 |
Time limit: | 1s-2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |