Wall [AtCoder Beginner Contest 079 D]

https://abc079.contest.atcoder.jp/tasks/abc079_d

前提知識

• ワーシャルフロイド法

解法

https://abc079.contest.atcoder.jp/submissions/1783444

数xを数yに変換するための最小コストを前もって計算しておこう。
これはワーシャルフロイド法を使えば10^3で行える。
あとは、数が書いてある全てのマスについて1に変換するコストの総和を取れば答え。

int H, W, C[10][10], A[202][202];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(i, 0, 10) rep(j, 0, 10) cin >> C[i][j];
    rep(y, 0, H) rep(x, 0, W) cin >> A[y][x];
 
    rep(k, 0, 10) rep(i, 0, 10) rep(j, 0, 10) C[i][j] = min(C[i][j], C[i][k] + C[k][j]);
    int ans = 0;
    rep(y, 0, H) rep(x, 0, W) if (0 <= A[y][x]) ans += C[A[y][x]][1];
    cout << ans << endl;
}