AT_iroha2019_day2_i 南極

在南极海域的地图上，有一个大小为 $H \times W$ 的网格。网格中的某个位置可以用坐标 $(i, j)$ 表示，其中 $i$ 表示从上往下的行数，而 $j$ 表示从左往右的列数。 海域中分布着许多冰山。探险家いろはちゃん想从起始位置 $(s_x, s_y)$ 移动到目标位置 $(g_x, g_y)$，每次只能向上下左右相邻的格子移动。由于某些格子上存在冰山，いろはちゃん无法直接通过，因此可能需要花费代价来融化这些冰山。 冰山的融化需要一些成本。融化编号为 $k$ 的冰山的费用为 $C_k$ 日元。你的任务是计算出让いろはちゃん从起点到达终点所需的最低成本。 在网格中，存在 $X$ 个不同的冰山。每个位置 $(i, j)$ 的状态用 $A_{i,j}$ 表示： - $A_{i,j} = 0$ 表示该位置无冰山； - $1 \leq A_{i,j} \leq X$ 表示此处有编号为 $A_{i,j}$ 的冰山。相同编号的冰山是相连的，也就是说它们之间是连续的。

从标准输入中读取以下内容： > $ H $ $ W $ $ X $ $ s_x $ $ s_y $ $ g_x $ $ g_y $ > $ A_{1,1} $ $ A_{1,2} \cdots A_{1,W} $ > $ A_{2,1} $ $ A_{2,2} \cdots A_{2,W} $ > $ \vdots $ > $ A_{H,1} $ $ A_{H,2} \cdots A_{H,W} $ > $ C_1 $ $ C_2 \cdots C_X $

输出从起点到终点所需的最小融化成本。

- 所有输入均为整数。 - $1 \leq H, W \leq 500$ - $1 \leq s_x, g_x \leq H$ - $1 \leq s_y, g_y \leq W$ - $(s_x, s_y)$ 和 $(g_x, g_y)$ 均不是冰山所在位置。 - $1 \leq X \leq HW - 2$ - $0 \leq A_{i,j} \leq X$ - 所有的编号从 $1$ 到 $X$ 的冰山编号 $A_{i,j}$ 均会出现。 - $1 \leq C_i \leq 10^{10}$ ### 部分得分信息 - 对于满足 $H, W \leq 40, X \leq 9$ 的所有测试用例，分数为 160 分。 - 对于满足 $H, W \leq 40$ 的所有测试用例，额外奖励 400 分。 - 对于所有测试用例，额外奖励 240 分。 ### 参考资料 [解题说明](https://img.atcoder.jp/iroha2019-day2/editorial-I.pdf) **本翻译由 AI 自动生成**