AT_iroha2019_day2_i 南極

[problemUrl]: https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_i 南極海は、$ 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} $ があることを表します。 ただし、同じ番号がついた氷山のマスは上下左右に連結です。

入力は以下の形式で標準入力から与えられます． > $ 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 $ (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 $点が与えられる ### 解説 [解説](https://img.atcoder.jp/iroha2019-day2/editorial-I.pdf)