Building Roads 道路建设的算法

Problem Description
There is a magic planet in the space. There is a magical country on the planet. There are N cities in the country. The country is magical because there are exactly N-1 magic roads between the N cities, and from each city, it is possible to visit any other city. But after the huge expansion of the country, the road system seems to be messy. The moderator decided to rebuild the road system.

As a worker, I cannot do too much things. I could just move one road to another position connecting arbitrary 2 cities using my magic, keeping its length unchanged. Of course, afterwards all the N cities have to be still connected. I wonder how to move in order to make the farthest distance between any two cities minimum. Could you solve it for me?

Input
The first line of the input is one integer T (T ≤ 10), and then T test cases follow.
Each test case begins with a line contains only one integer N (N ≤ 2500), means there are N magic cities. The cities are numbered from 0 to N-1.
Following N-1 lines, each line has 3 integers a, b and c, means there is a magic road between a and b with distance c. (0 <= a, b < N, 0 < c <= 1000)

Output
For each test case, output the case number and the corresponding minimum farthest distance. See sample for detailed format.

Sample Input
2
4
0 1 2
1 2 2
2 3 2
5
0 1 1
1 2 2
2 3 3
3 4 4

Sample Output
Case 1: 4
Case 2: 7

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问