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
mostafa_fares5:
2019-07-05 14:09:07
Last edit: 2019-07-05 14:32:11 |
|
bhavya_100000:
2019-07-02 06:20:24
Kruskals. AC in one go |
|
coder_19:
2019-05-29 10:47:10
100 means what??
|
|
zakir068:
2019-02-24 12:05:37
use long long
|
|
elmer_fudd:
2018-12-20 19:04:52
i get 100. is 100 means AC ? |
|
az2019:
2018-12-05 07:13:22
54 is wrong about capacity |
|
ameernsr:
2018-12-05 06:19:41
SALAM GUYS |
|
masterchef2209:
2018-10-17 15:34:28
100 with prims AC in one go \('_')/ |
|
hoang10tin:
2018-09-24 12:13:09
AC in one go :)))) |
|
Erick:
2018-07-27 23:30:00
AC in one go!! 100 :) |
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 |