Problem5711--最短的路5711: 最短的路
Time Limit: 1.000 Sec Memory Limit: 256 MB
Submit: 14 Solved: 3
[Submit] [Status] [Web Board] [Creator:]Description
你最近迷上了地理，你在家的时候会对着地图一看就是好久。有一天你在观察地图上的某一个区域的时候，发现有一块区域非常的特殊。这块区域一共有n个（n为偶数）城市，在这些城市中有n-1条道路连接，每条道路的长度都不一样。你现在想把这些城市两两分成一组，当两个城市被分到一组时，你会计算这两个城市之间的距离。现在你希望，分完以后n个城市以后，最小的距离和为多少？
Input
第一行输入一个数n，表示城市的数量。(1<=n<=10^4)
接下来输入n-1行，每行输入3个数u,v,w分别表示城市u到城市v存在一条长度为w的边。
(1<=u,v<=n,1<=w<=10^9,其中u不等于v)
Output
输出一个整数，表示最小的距离和
Sample Input
4
1 2 5
2 3 8
3 4 6
Sample Output
11
HINT
【输入样例2】
6
1 3 5
3 2 3
4 5 4
4 3 9
4 6 10
【输出样例2】
31
Source/Category
[Submit] [Status]