足跡-sokuseki-

りかの日進月歩の記録

ABC079 D Wall

D - Wall

問題概要

1つの数字を  i から  j に変えるコストを  c_{i,j} とする。
 H \times W 行列  A が与えられ、 A_{i,j} \neq -1 のとき上から  i 番目、左から  j 番目のマスに数字  A_{i,j} が書かれていて、  A_{i,j} = -1 のとき上から  i 番目、左から  j 番目のマスに数字が書かれていないことを意味する。
マスに書かれたすべての数字を1にする最小コストを答えよ。

制約
 1 \le H, W \le 200
 i \neq j のとき  1 \le c_{i,j} \le 10^3
 i = j のとき   c_{i,j} = 0
 -1 \le A_{i,j} \le 9

解法

数字を頂点番号だと思って、各頂点から頂点1への最短経路を求めます。(ワーシャルフロイドが一番書く量が少ないのでワーシャルフロイドを書いた)
あとはそれぞれの数字がマスにいくつ書かれているかを計算して、コストを掛けて出力する。

Submission #1965974 - AtCoder Beginner Contest 079