CF1517D Explorer Space

你正在 2050 会议的探索者空间中漫步。 探索者空间可以看作一个大小为 $n\times m$ 的无向带权网格图。顶点集合为 $\{(i, j)\mid 1\le i\le n, 1\le j\le m\}$。当且仅当 $|i_1-i_2|+|j_1-j_2|=1$ 时，顶点 $(i_1,j_1)$ 和 $(i_2, j_2)$ 之间有一条边相连。 每一步，你可以从当前位置走到与之相连的任意一个顶点。每条边上都有若干展品。由于你已经了解了所有展品，每当你经过一条包含 $x$ 个展品的边时，你的“无聊度”会增加 $x$。 对于每一个起点 $(i, j)$，请回答如下问题：如果你从 $(i, j)$ 出发，恰好走 $k$ 步后回到 $(i, j)$，最小可能的无聊度是多少？ 你可以多次经过同一条边，但每次经过时该边上的无聊度都会被计入多次。每一步你都不能停留在当前位置，也不能在经过一条边时中途改变方向。在回到起点 $(i, j)$ 之前，你可以自由地访问 $(i, j)$（也可以不访问）。

第一行包含三个整数 $n$、$m$ 和 $k$（$2\leq n, m\leq 500, 1\leq k\leq 20$）。 接下来的 $n$ 行中，第 $i$ 行的第 $j$ 个数（$1\le j \le m-1$）表示顶点 $(i, j)$ 和顶点 $(i, j+1)$ 之间的边上有多少展品。 接下来的 $n-1$ 行中，第 $i$ 行的第 $j$ 个数（$1\le j\le m$）表示顶点 $(i, j)$ 和顶点 $(i+1, j)$ 之间的边上有多少展品。 每条边上的展品数是一个 $1$ 到 $10^6$ 之间的整数。

输出 $n$ 行，每行 $m$ 个数。第 $i$ 行第 $j$ 个数 $answer_{ij}$ 表示从 $(i, j)$ 出发，恰好走 $k$ 步回到 $(i, j)$ 时最小可能的无聊度。 如果无法恰好走 $k$ 步回到 $(i, j)$，则 $answer_{ij}=-1$。

在第一个样例中，无论怎么走，答案始终为 $10$。 在第二个样例中，$answer_{21}=10$，路径为 $(2,1)\to(1,1)\to(1,2)\to(2,2)\to(2,1)$，无聊度为 $4+1+2+3=10$。 由 ChatGPT 4.1 翻译