Problem : 115 - 樹之國

Problem Statistics

Solved Member: 33　　Submission: 82　　User Tried: 33

Statement:

　　傳說中有一個遙遠的國度叫做樹之國。它之所以會被取名為樹之國，是因為這個國家裡面的都市和連接都市的道路會組成一棵樹，亦即不會有環的情況產生。這個國家一共有n個都市和n-1條道路。
　　在這個國家裡面有一臺造價不斐的傳送器，這台傳送器可以將樹之國的人從傳送器地點傳送到這個國家的任何一個地方。當然，這傳送的過程是走過連接城市的道路而不是直線距離。弔詭的是，這個傳送器是不需要軌道就可以傳送的，而這台傳送器的造價和離這台傳送器最遠的點的距離成正比。為了節省打造這台傳送器的費用，樹之國一定得在這個國家裡面找到一個最適合的位置放置這台機器。
　　現在假設每1單位距離就要耗費1單位打造費用，每0.1單位距離要耗費0.1單位，請你求出最少需要多少打造費用。
　　請注意，傳送器可以設置在道路中央。

Input:Output:

第1行是一個正整數n，代表總共有n個城市〈編號1~n〉。(1<=n<=100,000)
第2 ~ n行，每一行會有三個數字 p, q, v〈1<=v<=100〉，代表編號p和編號q的城市中間有一條長度為v的道路連接。

一個小數，到小數以下第一位，代表最少需要的打造費用。

Sample Input:Sample Output:

5
1 2 8
2 3 7
2 4 5
4 5 3

8.0

HINT:

出題者腦洞 4/8已經更新題目敘述

Source:

2012三龍盃程式設計競賽

Problem Setter

bigelephant29

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10