你是一只卖有趣算法问题的猫。今天,您想向 $$$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$$$。