Triangle City
题目描述
三角形城市有 n(n+1)/2 个路口,排成 n 行,第 i 行有 i 个路口。以 (i,j) 表示第 i 行第 j 列的路口。
所有道路均为双向道路。对每个 1≤j≤i<n,有:
- 长度为 ai,j 的道路连接 (i,j) 与 (i+1,j);
- 长度为 bi,j 的道路连接 (i,j) 与 (i+1,j+1);
- 长度为 ci,j 的道路连接 (i+1,j) 与 (i+1,j+1)。
此外,对所有 1≤j≤i<n,ai,j,bi,j,ci,j 都能作为一个非退化三角形的三条边。因此它们满足严格三角不等式:ai,j+bi,j>ci,j、ai,j+ci,j>bi,j、bi,j+ci,j>ai,j。这正是城市名称的由来。
著名旅行者 BaoBao 刚刚来到这里,准备从 (1,1) 出发,在 (n,n) 结束旅行。为了充分欣赏风景,他希望旅行路线尽可能长,同时每条道路至多经过一次。请输出这样一条最长路线。路口可以重复经过,但道路不能重复使用,反向经过同一道路也算重复。
输入格式
第一行包含整数 T,表示测试用例数。每个测试用例依次为:
第一行一个整数 n(2≤n≤300),表示城市的规模。
接下来 n−1 行,第 i 行给出 i 个整数 ai,1,…,ai,i。
再接下来 n−1 行,第 i 行给出 i 个整数 bi,1,…,bi,i。
再接下来 n−1 行,第 i 行给出 i 个整数 ci,1,…,ci,i。
所有道路长度均在 [1,109] 内,并满足上述严格三角不等式。保证同一输入文件中所有用例的 n 之和不超过 5×103。原题没有另行给出 T 的上限。
输出格式
每个测试用例恰好输出三行:
第一行一个整数 l,表示从 (1,1) 到 (n,n)、每条道路至多经过一次的最长路线长度。
第二行一个整数 m,表示路线上的路口个数。
第三行输出 2m 个整数 i1,j1,i2,j2,…,im,jm,以空格分隔,其中 (ik,jk) 是第 k 个经过的路口。必须有 (i1,j1)=(1,1) 和 (im,jm)=(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
样例说明
三个样例的城市如下图所示。第三个样例的路线多次经过同一路口,这是允许的。
