#P18445. Extending Distance

Extending Distance

Extending Distance

输入:标准输入;输出:标准输出。

给定按 nn 行、mm 列排列的 n×mn\times m 个点。记第 ii 行、第 jj 列的点为 (i,j)(i,j)。两个点 (i,j)(i,j)、(i′,j′)(i',j') 之间有一条带权双向边,当且仅当

∣i−i′∣+∣j−j′∣=1.|i-i'|+|j-j'|=1.

所有行、列下标均从 11 开始。

BaoBao 将从第一列的任意一点 (p,1)(p,1) 出发,在最后一列的任意一点 (q,m)(q,m) 结束旅程。所有边都可以双向经过;一条路径的长度等于经过的边的权值之和。BaoBao 会在所有从第一列到最后一列的路径中选择最短的一条。出发点和终点也由他自由选择。

为了让 BaoBao 更好地享受旅程,Little Cyan Fish 可以在出发前进行若干次操作:每次任选一条边,将其权值增加 11。他希望操作后,BaoBao 所选最短路径的长度恰好增加 kk。

请求出所需的最少操作次数,并输出一种达到此最小值的边权方案。只能增加边权,不能减小边权。

输入格式

第一行包含整数 TT,表示测试用例数。每个测试用例如下:

第一行包含三个整数 n,m,kn,m,k,满足

$$1\le nm\le500,\qquad 2\le n,m\le500,\qquad1\le k\le100.$$

接下来 nn 行,第 ii 行包含 m−1m-1 个整数 ri,1,…,ri,m−1r_{i,1},\ldots,r_{i,m-1}。其中 ri,jr_{i,j} 是点 (i,j)(i,j) 与 (i,j+1)(i,j+1) 之间的边权。

接下来 n−1n-1 行,第 ii 行包含 mm 个整数 ci,1,…,ci,mc_{i,1},\ldots,c_{i,m}。其中 ci,jc_{i,j} 是点 (i,j)(i,j) 与 (i+1,j)(i+1,j) 之间的边权。

所有原边权均满足 1≤ri,j,ci,j≤1091\le r_{i,j},c_{i,j}\le10^9。

保证一个输入文件内,所有测试用例的 nmnm 之和不超过 5×1035\times10^3。

输出格式

对于每个测试用例:

首先输出一行,一个整数,表示最少操作次数。

然后输出 nn 行,第 ii 行输出操作后的 ri,1′,…,ri,m−1′r'_{i,1},\ldots,r'_{i,m-1}。

然后输出 n−1n-1 行,第 ii 行输出操作后的 ci,1′,…,ci,m′c'_{i,1},\ldots,c'_{i,m}。

所有输出边权必须是整数,满足

$$r_{i,j}\le r'_{i,j}\le2\times10^9,\qquad c_{i,j}\le c'_{i,j}\le2\times10^9.$$

权值增加量之和必须等于报告的操作次数,最短路径长度必须恰好增加 kk。若最优方案不唯一,输出任意一种。

原题特别要求:每行末尾不要输出多余空格,否则可能被判为不正确。

原样例

2
3 4 6
2 1 15
7 1 9
13 3 2
3 6 1 2
5 2 15 3
3 3 3
1 1
2 2
3 3
1 1 1
2 2 2
9
2 3 15
7 1 10
13 3 4
3 6 3 2
5 4 15 3
4
4 1
3 2
3 3
1 1 1
2 2 2

样例说明

下图展示第一个测试用例。左侧为原图,右侧为增大部分边权后的图,红线标出了各自的一条最短路径。

第一个原样例的修改前后网格及红色最短路径

第一个测试用例原最短距离为 1212,修改后为 1818,增加 66,操作次数为 99。第二个测试用例原最短距离为 22,修改后为 55,增加 33,操作次数为 44。