CF2062F Traveling Salescat

You are a cat selling fun algorithm problems. Today, you want to recommend your fun algorithm problems to $ k $ cities. There are a total of $ n $ cities, each with two parameters $ a_i $ and $ b_i $ . Between any two cities $ i,j $ ( $ i\ne j $ ), there is a bidirectional road with a length of $ \max(a_i + b_j , b_i + a_j) $ . The cost of a path is defined as the total length of roads between every two adjacent cities along the path. For $ k=2,3,\ldots,n $ , find the minimum cost among all simple paths containing exactly $ k $ distinct cities.

The first line of input contains a single integer $ t $ ( $ 1 \leq t \leq 1500 $ ) — the number of test cases. For each test case, the first line contains a single integer $ n $ ( $ 2 \leq n \leq 3\cdot 10^3 $ ) — the number of cities. Then $ n $ lines follow, the $ i $ -th line contains two integers $ a_i,b_i $ ( $ 0 \leq a_i,b_i \leq 10^9 $ ) — the parameters of city $ i $ . It is guaranteed that the sum of $ n^2 $ over all test cases does not exceed $ 9\cdot 10^6 $ .

For each test case, print $ n-1 $ integers in one line. The $ i $ -th integer represents the minimum cost when $ k=i+1 $ .

In the first test case: - For $ k=2 $ , the optimal path is $ 1\to 2 $ with a cost of $ \max(0+1,2+2)=4 $ . - For $ k=3 $ , the optimal path is $ 2\to 1\to 3 $ with a cost of $ \max(0+1,2+2)+\max(0+3,3+2)=4+5=9 $ . In the second test case: - For $ k=2 $ , the optimal path is $ 1\to 4 $ . - For $ k=3 $ , the optimal path is $ 2\to 3\to 5 $ . - For $ k=4 $ , the optimal path is $ 4\to 1\to 3\to 5 $ . - For $ k=5 $ , the optimal path is $ 5\to 2\to 3\to 1\to 4 $ .