配点: 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