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
lokesh1997:
2017-08-02 15:11:02
what is this 18.18??
|
|
jainaman1398:
2017-07-18 15:48:28
I did this using prims.AC in one go |
|
trungpro:
2017-07-07 10:00:32
result is type long long in C++ or in64 in Pascal Last edit: 2017-07-07 10:01:08 |
|
onkar14_n:
2017-06-26 15:41:34
AC in one go !!
|
|
ravi_ndra12345:
2017-05-14 08:08:41
I am getting 81.82.
|
|
sidku97:
2017-04-26 17:14:46
Getting 18.18 and green colour?
|
|
diegoenojado:
2017-04-18 06:40:57
Is it possible to achieve 100 points with Prim algorithm? Couldnt make it |
|
sdfgsdgs:
2017-03-18 20:46:28
result 0 memory 0 time 0?
|
|
theo_pap1:
2017-03-04 16:23:12
I get 100 on result ... why isn't it accepted?
|
|
Sajal Sarkar:
2017-01-02 11:55:48
Aren't partial problems counted in solved problems? |
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 |