AtCoder BC079 D: Wall

問題

https://beta.atcoder.jp/contests/abc079/tasks/abc079_d

解法

各数字を1に書き換えるコストが最小になるようにし、その合計を出せば良い。

「1に書き換える最小コスト」＝「1への最短距離」と考えることが出来るので、事前にワーシャルフロイド法などで最短距離を求めておけば、あとは各Aijについて加算していけばよい。

実装

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstdlib>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int H,W;

    cin >> H >> W;

    int c[10][10];

    REP(i,10)REP(j,10){
        int tmp;
        cin >> tmp;
        c[i][j] = tmp; 
    }

    REP(i,10)REP(j,10)REP(k,10){
        c[j][k] = min(c[j][k], c[j][i] + c[i][k]);
    }

    int ans = 0;
    REP(i,H)REP(j,W){
        int a;
        cin >> a;
        if(a != -1 && a != 1){
            ans += c[a][1];
        }
    }

    cout << ans << endl;

}