F. Traveling Salescat
constructive algorithms; dp; geometry; graphs; greedy; math; sortings
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\).