#P18705. Triangle City

Triangle City

Triangle City

题目描述

三角形城市有 n(n+1)/2n(n+1)/2 个路口,排成 nn 行,第 ii 行有 ii 个路口。以 (i,j)(i,j) 表示第 ii 行第 jj 列的路口。

所有道路均为双向道路。对每个 1≤j≤i<n1\le j\le i<n,有:

  • 长度为 ai,ja_{i,j} 的道路连接 (i,j)(i,j) 与 (i+1,j)(i+1,j);
  • 长度为 bi,jb_{i,j} 的道路连接 (i,j)(i,j) 与 (i+1,j+1)(i+1,j+1);
  • 长度为 ci,jc_{i,j} 的道路连接 (i+1,j)(i+1,j) 与 (i+1,j+1)(i+1,j+1)。

此外,对所有 1≤j≤i<n1\le j\le i<n,ai,j,bi,j,ci,ja_{i,j},b_{i,j},c_{i,j} 都能作为一个非退化三角形的三条边。因此它们满足严格三角不等式:ai,j+bi,j>ci,ja_{i,j}+b_{i,j}>c_{i,j}、ai,j+ci,j>bi,ja_{i,j}+c_{i,j}>b_{i,j}、bi,j+ci,j>ai,jb_{i,j}+c_{i,j}>a_{i,j}。这正是城市名称的由来。

著名旅行者 BaoBao 刚刚来到这里,准备从 (1,1)(1,1) 出发,在 (n,n)(n,n) 结束旅行。为了充分欣赏风景,他希望旅行路线尽可能长,同时每条道路至多经过一次。请输出这样一条最长路线。路口可以重复经过,但道路不能重复使用,反向经过同一道路也算重复。

输入格式

第一行包含整数 TT,表示测试用例数。每个测试用例依次为:

第一行一个整数 nn(2≤n≤3002\le n\le300),表示城市的规模。

接下来 n−1n-1 行,第 ii 行给出 ii 个整数 ai,1,…,ai,ia_{i,1},\ldots,a_{i,i}。

再接下来 n−1n-1 行,第 ii 行给出 ii 个整数 bi,1,…,bi,ib_{i,1},\ldots,b_{i,i}。

再接下来 n−1n-1 行,第 ii 行给出 ii 个整数 ci,1,…,ci,ic_{i,1},\ldots,c_{i,i}。

所有道路长度均在 [1,109][1,10^9] 内,并满足上述严格三角不等式。保证同一输入文件中所有用例的 nn 之和不超过 5×1035\times10^3。原题没有另行给出 TT 的上限。

输出格式

每个测试用例恰好输出三行:

第一行一个整数 ll,表示从 (1,1)(1,1) 到 (n,n)(n,n)、每条道路至多经过一次的最长路线长度。

第二行一个整数 mm,表示路线上的路口个数。

第三行输出 2m2m 个整数 i1,j1,i2,j2,…,im,jmi_1,j_1,i_2,j_2,\ldots,i_m,j_m,以空格分隔,其中 (ik,jk)(i_k,j_k) 是第 kk 个经过的路口。必须有 (i1,j1)=(1,1)(i_1,j_1)=(1,1) 和 (im,jm)=(n,n)(i_m,j_m)=(n,n)。

若存在多个合法最优答案,可以输出其中任意一个。

请勿在任何一行末尾输出多余空格,否则可能被判为错误。

样例输入

3
2
3
2
4
2
1
1
1
3
100
100 100
1
100 1
100
100 100

样例输出

7
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

样例说明

三个样例的城市如下图所示。第三个样例的路线多次经过同一路口,这是允许的。

原题三个样例的城市示意图