ABC079 D Wall
問題概要
1つの数字を から に変えるコストを とする。
行列 が与えられ、 のとき上から 番目、左から 番目のマスに数字 が書かれていて、 のとき上から 番目、左から 番目のマスに数字が書かれていないことを意味する。
マスに書かれたすべての数字を1にする最小コストを答えよ。
制約
のとき
のとき
解法
数字を頂点番号だと思って、各頂点から頂点1への最短経路を求めます。(ワーシャルフロイドが一番書く量が少ないのでワーシャルフロイドを書いた)
あとはそれぞれの数字がマスにいくつ書かれているかを計算して、コストを掛けて出力する。