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
abdelhameedddd:
2018-07-19 02:19:30
ac in one go
|
|
cnavneet:
2018-07-11 19:32:46
AC in one go.. Simple problem based on Kruskal's minimum spanning tree.. |
|
vd09:
2018-07-08 20:08:36
stuck in 91.92 point, what should i do now?
|
|
adityad1998:
2018-06-30 09:25:52
Simple Kruskal,exactly same as https://www.spoj.com/problems/CSTREET/. |
|
coollllmann:
2018-05-04 15:08:21
int score: 81.82
|
|
ameyanator:
2018-04-25 08:31:01
81.82 points with int data type and 100 with long long int |
|
ayushtewary07:
2018-02-17 16:21:33
Accepted in one go!
|
|
ramini1996:
2018-01-30 21:14:04
100 with Kruskal, AC in one go !!! |
|
ramprosad:
2017-11-07 15:24:49
why isn't it accepted? I get 100 point.
|
|
amit88265:
2017-08-23 19:02:33
i am using long long but still getting 18.18 and green!!!!!!....someone help please. |
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 |