#P18715. Travelling
Travelling
Travelling
有 座城市,编号 ,以及连接它们的 条双向道路。任意两座城市之间都存在路径。第 条道路连接 ,每经过一次花费 枚硬币。
你从城市 出发,要访问所有城市,最后回到城市 。每秒可以沿一条道路从当前城市移动到相邻城市,并支付这条道路的费用。每条道路至多经过两次。 当你已经访问所有城市且回到城市 时,可以结束旅行。总费用是所有移动费用之和。
给定一个整数 。旅行中可以使用一张免费券一次,使得接下来的连续 次移动不需要付费。
对每个 ,分别求访问所有城市、回到城市 ,且最优使用免费券时的最小总费用。不同 可以选择不同的旅行路线。
输入格式
第一行一个整数 (),表示测试用例数。每个测试用例如下:
第一行一个整数 ()。随后 行,第 行三个整数 (,),描述第 条双向道路。
保证任意两点之间有路径。所有测试用例的 之和不超过 。道路费用允许为 。
输出格式
每个测试用例输出一行 个整数,按顺序给出 的答案。
原样例
2
5
1 2 2
2 3 3
2 4 1
4 5 3
7
1 2 1
1 3 1
1 4 4
3 5 5
3 6 1
6 7 4
18 15 12 10 8 5 3 2 0
32 27 22 21 17 13 12 8 4 3 2 1 0
原样例说明
第一个测试用例中,下面同一条路线对所有 都可以达到最优:
对应的费用序列是 。各 可选的免费片段如下(与原表一致):
| 免费费用片段 | 答案 | |
|---|---|---|
| 0 | 18 | |
| 1 | 15 | |
| 2 | 12 | |
| 3 | 10 | |
| 4 | 8 | |
| 5 | 5 | |
| 6 | 3 | |
| 7 | 2 | |
| 8 | 0 |
| 免费片段 | 答案 | |
|---|---|---|
| 0 | [] | 18 |
| 1 | [3] | 15 |
| 2 | [3, 3] | 12 |
| 3 | [2, 3, 3] | 10 |
| 4 | [3, 3, 1, 3] | 8 |
| 5 | [3, 3, 1, 3, 3] | 5 |
| 6 | [2, 3, 3, 1, 3, 3] | 3 |
| 7 | [2, 3, 3, 1, 3, 3, 1] | 2 |
| 8 | [2, 3, 3, 1, 3, 3, 1, 2] | 0 |