← 返回题目列表

Codeforces · 1520/G

G. 去还是不去?

中文机器翻译题面 查看原题

迪马睡过了闹钟,而闹钟本应送他去学校。

Dima 想知道他是否有时间来上第一节课。为此,他需要知道从家到学校所需的最短时间。

Dima 居住的城市是一个 $$$n \times m$$$ 大小的矩形区域。该字段中的每个单元格 $$$(i, j)$$$ 由一个数字 $$$a_{ij}$$$ 表示:

- 数字$$$-1$$$表示禁止通过该牢房;
- 数字 $$$0$$$ 表示牢房是空闲的,迪玛可以穿过它。
- 数字 $$$x$$$ ($$$1 \le x \le 10^9$$$) 表示该单元格包含一个成本为 $$$x$$$ 的传送门。具有门户的单元也被认为是免费的。

从任何传送门,Dima 都可以前往任何其他传送门,而从传送门 $$$(i, j)$$$ 移动到传送门 $$$(x, y)$$$ 的时间对应于其成本 $$$a_{ij} + a_{xy}$$$ 的总和。

除了在传送门之间移动之外,Dima 还可以在时间 $$$w$$$ 的一侧相邻的空闲单元格之间移动。特别是,他可以进入带有传送门的牢房而不使用它。

最初,Dima 位于左上角单元格 $$$(1, 1)$$$,学校位于右下角单元格 $$$(n, m)$$$。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$w$$$ ($$$2 \le n, m \le 2 \cdot 10^3$$$, $$$1 \le w \le 10^9$$$),其中 $$$n$$$ 和 $$$m$$$ 是城市大小,$$$w$$$ 是时间迪马在空闲的牢房之间移动。

接下来的 $$$n$$$ 行每行包含 $$$m$$$ 数字 ($$$-1 \le a_{ij} \le 10^9$$$) — 单元格的描述。

保证单元格 $$$(1, 1)$$$ 和 $$$(n, m)$$$ 是空闲的。

输出

输出 Dima 到达学校所需的最短时间。如果他根本无法去学校,则输出“-1”。

示例

输入 #1

5 5 1
0 -1 0 1 -1
0 20 0 0 -1
-1 -1 -1 -1 -1
3 0 0 0 0
-1 0 0 0 0

输出 #1

14

注意

第一个样本的说明: