
ZOJ Problem Set  4122
Triangle City is a city with $\frac{n(n+1)}{2}$ intersections arranged into $n$ rows and $n$ columns, where the $i$th row contains $i$ intersections. The intersections are connected by bidirectional roads. Formally, if we denote $(i, j)$ as the intersection on the $i$th row and the $j$th column, for all $1 \le j \le i < n$,
What's more, for all $1 \le j \le i < n$, there exists a triangle whose sides are of length $a_{i, j}$, $b_{i, j}$ and $c_{i, j}$. That's why the city is called the Triangle City! Our famous traveler BaoBao has just arrived in the Triangle City, planning to start his journey from intersection $(1, 1)$ and end his trip at intersection $(n, n)$. To fully enjoy the landscape, BaoBao would like to find the longest path from $(1, 1)$ to $(n, n)$ such that each road is passed no more than once. Please help BaoBao find such a path. Recall that if the sides of a triangle are of length $a$, $b$ and $c$, we can infer that $a + b > c$, $a + c > b$ and $b + c > a$. InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains an integer $n$ ($2 \le n \le 300$), indicating the size of the city. For the following $(n  1)$ lines, the $i$th line contains $i$ integers $a_{i, 1}, a_{i, 2}, \dots, a_{i, i}$ ($1 \le a_{i, j} \le 10^9$), where $a_{i, j}$ indicates the length of the road connecting intersection $(i, j)$ and $(i + 1, j)$. For the following $(n  1)$ lines, the $i$th line contains $i$ integers $b_{i, 1}, b_{i, 2}, \dots, b_{i, i}$ ($1 \le b_{i, j} \le 10^9$), where $b_{i, j}$ indicates the length of the road connecting intersection $(i, j)$ and $(i + 1, j + 1)$. For the following $(n  1)$ lines, the $i$th line contains $i$ integers $c_{i, 1}, c_{i, 2}, \dots, c_{i, i}$ ($1 \le c_{i, j} \le 10^9$), where $c_{i, j}$ indicates the length of the road connecting intersection $(i + 1, j)$ and $(i + 1, j + 1)$. It's guaranteed that the sum of $n$ of all test cases will not exceed $ 5 \times 10^3$. OutputFor each test case output three lines. The first line contains one integer $l$, indicating the length of the longest path from $(1, 1)$ to $(n, n)$ such that each road is passed no more than once. The second line contains one integer $m$, indicating the number of intersections on the longest path. The third line contains $2m$ integers $i_1, j_1, i_2, j_2, \dots, i_m, j_m$ separated by a space, where $(i_k, j_k)$ indicates the $k$th intersection on the longest path. Note that according to the description, there must be $(i_1, j_1) = (1, 1)$ and $(i_m, j_m) = (n, n)$. If there are multiple valid answers, you can output any of them. Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect! Sample Input3 2 3 2 4 2 1 1 1 3 100 100 100 1 100 1 100 100 100 Sample Output7 3 1 1 2 1 2 2 2 3 1 1 2 1 2 2 700 8 1 1 2 1 3 2 2 2 2 1 3 1 3 2 3 3 HintThe sample test cases are shown below: Author: WENG, Caizhi Source: The 10th Shandong Provincial Collegiate Programming Contest 