← 返回题目列表

AtCoder · iroha2019_day2_i

I. 南极洲

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

 配点: 800 点

問題文

南大洋是 它由H \times W 网格表示。从海上 i 正方形,从左起 j 方形部分 (i, j) 代表。

南大洋有很多冰山。伊吕波酱是一位探险家。 我想重复向上、向下、向左、向右移动到相邻的方块,直到(s_x, s_y) 不同编号的点最多为 (g_x, g_y) 。你可能需要融化一些冰山,因为你无法将它们移动到它们所在的广场。

每座冰山都有固定的融化成本。k 融化所有冰山的成本是 C_k 是日元。 伊吕波酱 达到 (s_x, s_y) 不同编号的点最多为 (g_x, g_y) 的最低成本是多少?

冰山是 有 X 件。鳟鱼 (i, j) 的状态是 A_{i,j} 。 A_{i,j} = 0 表示这个广场上没有冰山。 当 1 \leq A_{i,j} \leq X 时,这个广场上有一座冰山。 A_{i,j} 存在。 然而,相同数量的冰山方格是垂直和水平连接的。

制約

  • 输入都是整数
  • 1 \leq H, W \leq 500
  • 1 \leq s_x, g_x \leq H (2019/05/01 13:45 追記)
  • 1 \leq s_y, g_y \leq W (2019/05/01 13:45 追記)
  • (s_x, s_y), (g_x, g_y) 都是不是冰山的正方形。
  • 1 \leq X \leq HW - 2
  • 0 \leq A_{i,j} \leq X
  • A_{i,j} 至 包含所有 1, 2, 3, \dots, X 如果您正确回答了满足
  • 1 \leq C_i \leq 10^{10}

部分点

  • H, W \leq 40, X \leq 9 的所有测试用例,160 点。
  • H, W \leq 40 的所有测试用例,进一步 400 点。
  • 如果您正确回答所有测试用例,进一步240积分已给出

入力

输入是按以下格式从标准输入给出的。

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

4 5 4
2 1
3 5
1 1 1 2 2
0 1 0 2 0
0 3 0 4 0
3 3 4 4 4
10 5 8 12

出力例 1

13

入力例 2

5 7 6
5 3
2 7
2 2 2 1 1 3 3
2 2 2 1 1 3 0
2 6 6 6 1 3 5
2 6 6 6 1 4 4
2 2 0 1 1 4 4
927 138 284 714 456 798

出力例 2

1211

解説

解説