交换房子 Holiday's Accommodatio
题意翻译
### 翻译:
有n个城市，n-1条双向公路，每个城市有一个人，他们都想去另一个城市游玩，且每个人所选城市不同。找出一个最优方案使每个人的行程和最大，且每个人总是选择他所在城市到所选城市的最短路径。
### 输入:
第一行输入一个正整数t(1≤t≤10)表示测试用例的数量
对于每个测试用例给出一个正整数n(2≤n≤105)
下面n-1行每行给出三个正整数x,y,z(1≤x,y≤n,1≤z≤106)表示有一条连接x,y的双向公路,长度为z
### 输出:
对于每个测试用例,输出一行```Case #X: Y```,X表示是第几个用例,Y表示最优方案下的行程和
### 样例输入:
```
2
4
1 2 3
2 3 2
4 3 2
6
1 2 3
2 3 4
2 4 1
4 5 8
5 6 5
```
### 样例输出:
```
Case #1: 18
Case #2: 62
```
by_心有灵一点通2019/11/2
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=825&page=show_problem&problem=4544
[PDF](https://uva.onlinejudge.org/external/16/p1669.pdf)