Sleigh Ride
Now that Santa's put all the presents in his magic bag, he's going to go deliver the presents!Of course, he's going to fly in the sky with the help of his trusty reindeer.
(How he delivers everything in time is another story..)
Santa starts at the North Pole, and must visit several (N) locations.
But he can't just travel however he wants.
Terrorists might try hunting him, or he might get shot down in protected airspace...
Also, some routes are really slow because of air currents.
Thus Santa has exactly N possible routes to travel. (However, it's still guaranteed he'll be able to deliver everything)
The routes are all two-way.
Given a list of these routes, output the time it takes for Santa to deliver the presents to every location!
Santa can visit places in any order, though.
Input:
N (number of locations, 1 ≤ N ≤ 100,000)N lines, each with three integers a,b,c (0 ≤ a,b ≤ N, 0 ≤ c ≤ 1,000)
Each line represents a route between locations a and b, that takes c seconds to traverse.
(Location 0 is the North Pole)
Output:
The minimum time it takes to deliver presents everywhere.He won't have to return to the North Pole.
Sample Input:
2 0 1 1 0 2 1
Sample Output:
3
Santa goes from the North Pole to location 1 (+1 second), back to the North Pole (+1 second), and finally to location 2 (+1 second).
All Submissions
Best Solutions
Point Value: 10
Time Limit: 1.00s
Memory Limit: 32M
Added: Dec 20, 2008
Author: hansonw1
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
It's quiet in here...