Sphere Online Judge

SPOJ Problem Set (partial)

3188. Minimum Spanning Tree

Problem code: MST


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

Added by:Nikola P Borisov
Date:2008-10-20
Time limit:5s-10s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: ERL JS NODEJS PERL 6

hide comments
2014-06-14 10:29:43 ayush
Thank You Aman
2014-01-22 18:36:32 elgun
AC
[code removed]

See notes at bottom: "1. Don't post any source code here."

Last edit: 2014-01-22 22:05:08
2014-01-15 17:51:31 dslearner
isnt this problem same as http://www.spoj.com/problems/CSTREET/
but getting runtime in CSTREET while got this one accepted ....plz help

Last edit: 2014-01-15 17:56:55
2013-09-02 05:29:48 William Macfarlane
Aman Gupta,
Thank you so much for the tip. I was getting 81.82.
2013-06-12 10:18:48 Avneet
my solution got accepted , but result is 0 , wht it means ?
2013-01-10 10:55:14 Lại Mạnh Tuấn
@ Aman Gupta: Thanks for the suggestion
2012-10-08 17:52:24 Aman Gupta
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
2012-08-01 00:32:15 Haidar Abboud
hope to see more textbook problems like this one -- useful to test the efficiency of your implementation
2012-02-24 15:19:49 Giorgos Christoglou
@ Nicolas i quess WA ...
2010-12-21 06:22:26 .::Manish Kumar::.


Last edit: 2012-03-30 11:48:26
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.