幹線道路 (Trunk Road) [JOI/IOI 第17回日本情報オリンピック 予選 C]

https://atcoder.jp/contests/joi2018yo/tasks/joi2018_yo_c

解法

https://atcoder.jp/contests/joi2018yo/submissions/8137095

幹線道路となる道路を全探索する。
H本の道路からsy番目、W本の道路からsx番目を選ぶとする。
あとは、その道路と全ての交差点について距離を計算し、距離×人数の総和の最小値を求めていけばいい。

int H, W, A[30][30];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) rep(x, 0, W) cin >> A[y][x];

    int ans = inf;
    rep(sy, 0, H) rep(sx, 0, W) {
        int sm = 0;
        rep(y, 0, H) rep(x, 0, W) {
            int dy = abs(sy - y);
            int dx = abs(sx - x);
            int d = min(dx, dy);
            sm += d * A[y][x];
        }
        chmin(ans, sm);
    }
    cout << ans << endl;
}