ABC079: D - Wall

問題

D - Wall

解説

各に対して割にコストを独立に計算して良い。についてワーシャルフロイドしておけば、0-9から1にするまでの最小コストが求まる。

一度の変更がグリッド上の複数マスに同時に起こるような形ならマラソン系の問題になるのだろうか。

int main() {
  int H, W; cin >> H >> W;
  vector<vector<int>> c(10, vector<int>(10));
  rep(i, 10) cin >> c[i];
  rep(k, 10) rep(i, 10) rep(j, 10) {
    minimize(c[i][j], c[i][k] + c[k][j]);
  }
  vector<vector<int>> A(H, vector<int>(W));
  rep(i, H) cin >> A[i];
  int count = 0;
  rep(i, H) rep(j, W) if (A[i][j] > -1) {
    count += c[A[i][j]][1];
  }
  cout << count << "\n";
}