#P18445. Extending Distance
Extending Distance
Extending Distance
输入:标准输入;输出:标准输出。
给定按 行、 列排列的 个点。记第 行、第 列的点为 。两个点 、 之间有一条带权双向边,当且仅当
所有行、列下标均从 开始。
BaoBao 将从第一列的任意一点 出发,在最后一列的任意一点 结束旅程。所有边都可以双向经过;一条路径的长度等于经过的边的权值之和。BaoBao 会在所有从第一列到最后一列的路径中选择最短的一条。出发点和终点也由他自由选择。
为了让 BaoBao 更好地享受旅程,Little Cyan Fish 可以在出发前进行若干次操作:每次任选一条边,将其权值增加 。他希望操作后,BaoBao 所选最短路径的长度恰好增加 。
请求出所需的最少操作次数,并输出一种达到此最小值的边权方案。只能增加边权,不能减小边权。
输入格式
第一行包含整数 ,表示测试用例数。每个测试用例如下:
第一行包含三个整数 ,满足
$$1\le nm\le500,\qquad 2\le n,m\le500,\qquad1\le k\le100.$$接下来 行,第 行包含 个整数 。其中 是点 与 之间的边权。
接下来 行,第 行包含 个整数 。其中 是点 与 之间的边权。
所有原边权均满足 。
保证一个输入文件内,所有测试用例的 之和不超过 。
输出格式
对于每个测试用例:
首先输出一行,一个整数,表示最少操作次数。
然后输出 行,第 行输出操作后的 。
然后输出 行,第 行输出操作后的 。
所有输出边权必须是整数,满足
$$r_{i,j}\le r'_{i,j}\le2\times10^9,\qquad c_{i,j}\le c'_{i,j}\le2\times10^9.$$权值增加量之和必须等于报告的操作次数,最短路径长度必须恰好增加 。若最优方案不唯一,输出任意一种。
原题特别要求:每行末尾不要输出多余空格,否则可能被判为不正确。
原样例
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
样例说明
下图展示第一个测试用例。左侧为原图,右侧为增大部分边权后的图,红线标出了各自的一条最短路径。

第一个测试用例原最短距离为 ,修改后为 ,增加 ,操作次数为 。第二个测试用例原最短距离为 ,修改后为 ,增加 ,操作次数为 。