AtCoder ABC 079 D - Wall (緑色, 400 点)

Floyd--Warshall と、あとグリッド上の各マスは独立に考えて OK。

問題へのリンク

問題概要

のグリッドがあって、各マスには -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 のいずれかの数値が書かれている。目的は -1 以外のマスをすべて 1 に変えることである。

各マスに対して、数値 i が書かれている状態から数値 j が書かれている状態に変更するのにかかるコストは c[ i ][ j ] で与えられる。

目的を達するための最小コストを求めよ。

制約

• 

考えたこと

各マスごとに独立に考えて良いことに注意する。一般に、

• 色 i を色 1 にするのに必要な最小コスト

が求められたら良い。これは Floyd--Warshall 法などによって、「全頂点間の最短路長」をスパッと求めてしまうのが楽そう。

#include <bits/stdc++.h>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF = 1<<29;
int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<int>> c(10, vector<int>(10, INF));
    for (int i = 0; i < 10; ++i) for (int j = 0; j < 10; ++j) cin >> c[i][j];
    for (int k = 0; k < 10; ++k)
        for (int i = 0; i < 10; ++i) 
            for (int j = 0; j < 10; ++j)
                chmin(c[i][j], c[i][k] + c[k][j]);
    long long res = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            int A; cin >> A;
            if (A == -1) continue;
            res += c[A][1];
        }
    }
    cout << res << endl;
}