AOJ 2302 On or Off

競プロ AOJ

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2302

問題概要

R * C のグリッドが与えられる．各マスは，部屋または壁を表している．
さらに，M 個の仕事が与えられて，それぞれの仕事をする部屋は決められている．仕事は与えられた順番にこなす必要がある．
部屋には電気のスイッチがあって，部屋に入るためには電気をつけなければならない．
部屋から出るときは，電気を消すか，つけっぱなしにするか選ぶことができる．ただし，全ての仕事を終えた時，全ての部屋の電気は消されていなければならない．
電気をつける時のコスト，消す時のコスト，つけっぱなしにしたときの単位時間あたりのコストが与えられる．
このとき，全ての仕事を片付けるのに，消費電力を最小化したい．
最小化した時の消費電力を求めよ．

・制約
1 <= R <= 50
1 <= C <= 50
2 <= M <= 1000
任意の2つの部屋を結ぶ道は，ただひとつしかない（つまり部屋は木構造になっている）．　←冒頭にさらっと書かれているが重要な制約．見落とさないように！
（コストの制約が書かれていないが，求める答えは int の表現幅を超えないとして良いようだ）

解法

BFS(経路復元あり) + 貪欲？

木構造になっている条件を見逃すと，僕のように時間を浪費するので気をつけたい．
木構造になっているので，最初の仕事をしてから最後の仕事をするまでの道筋が一意に定まる．
なので，各部屋を訪れる時刻が一意に定まる．（別の時刻に同じ部屋を通ることもある．）
あとでどの部屋を通ったのかを調べないといけないので，経路復元用のデータを作る必要がある．
さて，ある部屋を1度しか通らない場合は，最終的に消えていないといけないので，つけるコスト＋消すコストでよい．
同じ部屋を2回以上通る場合，前回通った時につけっぱなしにすべきかどうかの選択をしなければならない．
ある部屋を i 回目に通った時刻が t[i] で， i-1 回目に通った時刻が t[i-1] だとする．
i-1 回目につけっぱなしにしていれば，(単位時間コスト) * (t[i] - t[i-1]) だけコストがかかり，消していれば再度つけて消すので (つけるコスト) + (消すコスト) がかかる．
これらのうち小さいほうを複数回通るたびに貪欲に選んでいけばよい．

計算量は O(RCM)．

ソースコード

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using P = pair<int, int>;

constexpr int INF = 1e9;

int main() {
    int R, C, M;
    cin >> R >> C >> M;
    vector<string> v(R);
    for(int i=0; i<R; ++i) {
        cin >> v[i];
    }
    // 0: per, 1: on, 2: off
    vector<vector<vector<int>>> cost(3, vector<vector<int>>(R, vector<int>(C)));
    for(int i=0; i<3; ++i) {
        for(int j=0; j<R; ++j) {
            for(int k=0; k<C; ++k) {
                cin >> cost[i][j][k];
            }
        }
    }
    vector<P> task(M);
    for(int i=0; i<M; ++i) {
        cin >> task[i].first >> task[i].second;
    }
    int res = cost[1][task[0].first][task[0].second] + cost[2][task[0].first][task[0].second];
    vector<vector<int>> prev_t(R, vector<int>(C, INF));
    prev_t[task[0].first][task[0].second] = 0;
    int t = 0;
    for(int i=1; i<M; ++i) {
        queue<P> que;
        que.push(task[i-1]);
        vector<vector<int>> d(R, vector<int>(C, INF));
        vector<vector<P>> prev(R, vector<P>(C, P{-1, -1}));
        d[task[i-1].first][task[i-1].second] = t;
        while(!que.empty()) {
            P p = que.front(); que.pop();
            int dr[4] = {0, 1, 0, -1},
                dc[4] = {1, 0, -1, 0};
            for(int j=0; j<4; ++j) {
                int nr = p.first + dr[j],
                    nc = p.second + dc[j];
                if(nr < 0 || R <= nr || nc < 0 || C <= nc || v[nr][nc] == '#') {
                    continue;
                }
                if(d[nr][nc] == INF) {
                    d[nr][nc] = d[p.first][p.second] + 1;
                    prev[nr][nc] = p;
                    que.push(make_pair(nr, nc));
                }
            }
        }
        int r = task[i].first, c = task[i].second;
        t = d[r][c];
        while(r != task[i-1].first || c != task[i-1].second) {
            if(prev_t[r][c] != INF) {
                res += min((d[r][c] - prev_t[r][c]) * cost[0][r][c], cost[1][r][c] + cost[2][r][c]);
            } else {
                res += cost[1][r][c] + cost[2][r][c];
            }
            prev_t[r][c] = d[r][c];
            P p = prev[r][c];
            r = p.first, c = p.second;
        }
    }
    cout << res << endl;
}

感想