← 返回题目列表

Codeforces · 2062/F

F. 旅行推销员

中文机器翻译题面 查看原题

你是一只卖有趣算法问题的猫。今天,您想向 $$$k$$$ 城市推荐您有趣的算法问题。

总共有 $$$n$$$ 个城市,每个城市有两个参数 $$$a_i$$$ 和 $$$b_i$$$。任意两个城市 $$$i,j$$$ ($$$i\ne j$$$) 之间,有一条双向道路,长度为 $$$\max(a_i + b_j , b_i + a_j)$$$。路径成本定义为沿路径每两个相邻城市之间的道路总长度。

对于 $$$k=2,3,\ldots,n$$$,找到包含 $$$k$$$ 不同城市的所有简单路径中的最小成本。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1500$$$) — 测试用例的数量。

对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 3\cdot 10^3$$$) — 城市数量。

接下来是 $$$n$$$ 行,第 $$$i$$$ 行包含两个整数 $$$a_i,b_i$$$ ($$$0 \leq a_i,b_i \leq 10^9$$$) — 城市 $$$i$$$ 的参数。

保证所有测试用例的$$$n^2$$$总和不超过$$$9\cdot 10^6$$$。

输出

对于每个测试用例,在一行中打印 $$$n-1$$$ 整数。第$$$i$$$个整数表示$$$k=i+1$$$时的最小成本。

示例

输入 #1

3
3
0 2
2 1
3 3
5
2 7
7 5
6 3
1 8
7 5
8
899167687 609615846
851467150 45726720
931502759 23784096
918190644 196992738
142090421 475722765
409556751 726971942
513558832 998277529
294328304 434714258

输出 #1

4 9 
10 22 34 46 
770051069 1655330585 2931719265 3918741472 5033924854 6425541981 7934325514

注意

在第一个测试用例中:

- 对于 $$$k=2$$$,最佳路径是 $$$1\to 2$$$,成本为 $$$\max(0+1,2+2)=4$$$。
- 对于$$$k=3$$$,最佳路径是$$$2\to 1\to 3$$$,成本为$$$\max(0+1,2+2)+\max(0+3,3+2)=4+5=9$$$。

在第二个测试用例中:

- 对于 $$$k=2$$$,最佳路径是 $$$1\to 4$$$。
- 对于 $$$k=3$$$,最佳路径是 $$$2\to 3\to 5$$$。
- 对于 $$$k=4$$$,最佳路径是 $$$4\to 1\to 3\to 5$$$。
- 对于 $$$k=5$$$,最佳路径是 $$$5\to 2\to 3\to 1\to 4$$$。