#P17396. [ICPC 2023 Nanjing R] 延伸距离

[ICPC 2023 Nanjing R] 延伸距离

题目描述

有 n×mn\times m 个点排成 nn 行 mm 列,相邻点之间被无向带权边连接。

令 (i,j)(i,j) 表示位于第 ii 行第 jj 列的点。对于所有 1≤i,i′≤n1\le i,i'\le n 和 1≤j,j′≤m1\le j,j'\le m,当且仅当 ∣i−i′∣+∣j−j′∣=1|i-i'|+|j-j'|=1 时,(i,j)(i,j) 与 (i′,j′)(i',j') 之间有一条无向边。

堡堡的旅行从第一列的任意一点 (p,1)(p,1) 出发,在最后一列的任意一点 (q,m)(q,m) 结束。对于每条边,他都可以沿任意方向通过。

一条路径的距离定义为该路径经过的所有边的边权之和。在所有从第一列到最后一列的路径中,堡堡会选择距离最短的一条,因此旅行距离等于第一列到最后一列的最短路长度。

小青鱼希望堡堡能够多享受一会儿旅程,因此会在堡堡出发前增加一些边的权值。每次操作可以选择任意一条边,将其权值增加 11。

小青鱼希望经过若干次操作后,第一列到最后一列的最短路长度恰好增加 kk。

请计算最少需要进行多少次操作。

本题由原题改编。原题还要求输出一种最优修改方案,本版本只需要输出最少操作次数。

输入格式

有多组测试数据。

第一行输入一个整数 TT,表示测试数据组数。

对于每组测试数据:

第一行输入三个整数 n,m,kn,m,k,其中 nn、mm 分别表示网格的行数和列数,kk 表示要求最短路增加的距离。

接下来 nn 行,第 ii 行输入 m−1m-1 个整数

ri,1,ri,2,…,ri,m−1r_{i,1},r_{i,2},\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,2,…,ci,mc_{i,1},c_{i,2},\ldots,c_{i,m},

其中 ci,jc_{i,j} 表示连接 (i,j)(i,j) 与 (i+1,j)(i+1,j) 的纵向边的权值。

输出格式

对于每组测试数据,输出一行一个整数,表示使第一列到最后一列的最短路长度恰好增加 kk 所需的最少操作次数。

输入输出样例 #1

输入 #1

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

输出 #1

9
4

说明/提示

对于样例中的第一组数据,至少需要进行 99 次操作,才能使第一列到最后一列的最短路长度恰好增加 66。

对于样例中的第二组数据,至少需要进行 44 次操作,才能使最短路长度恰好增加 33。

数据范围

对于所有测试数据,保证:

  • 2≤n,m≤5002\le n,m\le 500;
  • n×m≤500n\times m\le 500;
  • 1≤k≤1001\le k\le 100;
  • 1≤ri,j,ci,j≤1091\le r_{i,j},c_{i,j}\le 10^9;
  • 单个输入文件中所有测试数据的 n×mn\times m 之和不超过 5×1035\times 10^3。