Codeforces Round #355 (Div. 2) D. Vanya and Treasure

問題
Problem - D - Codeforces
の部屋があり，それぞれ宝箱が置いてある．タイプの宝箱にはタイプの宝箱を開ける鍵が入っている．タイプの宝箱を開けるまでに移動する最小距離はいくつか．

解法
単純にタイプごとにダイクストラを行っていたら間に合わない．そこでタイプの宝箱がある位置を配列で持っておき，タイプからタイプの全組み合わせを列挙して最小距離を求める．しかし，最悪の場合の組み合わせがあるのでこれもまた間に合わない．[タイプの数タイプの数]が一定以上になったらダイクストラで探索をすることで最悪の場合を回避できる．

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;

#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP (i,0,(int)(n)-1)
#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP (i,(int)(n)-1,0)
#define INF (int)1e8
#define MOD (int)(1e9+7)

typedef long long ll;

int dist2[300][300];
int dist[300][300];
int a[300][300];
vector<pair<int,int>> chest[90001];

int main(void) {
    int i, j, n, m, p, t;
    cin >> n >> m >> p;
    rep (i,n) rep (j,m) {
        cin >> a[i][j];
        chest[a[i][j]].push_back(make_pair(i,j));
        if (a[i][j] == 1)
            dist[i][j] = i+j;
        else
            dist[i][j] = INF;
    }
    REP (t,2,p) {
        if (chest[t].size() * chest[t-1].size() < 1000000) for (auto p : chest[t]) for (auto q : chest[t-1])
            dist[p.first][p.second] = min(dist[p.first][p.second],dist[q.first][q.second]+abs(p.first-q.first)+abs(p.second-q.second));
        else {
            priority_queue<pair<int,pair<int,int>>> q;
            for (auto p : chest[t-1]) q.push(make_pair(-dist[p.first][p.second],p));
            rep (i,n) rep (j,m) {
                if (a[i][j] == t-1)
                    dist2[i][j] = dist[i][j];
                else
                    dist2[i][j] = INF;
            }
            while (!q.empty()) { 
                int d = -q.top().first + 1;
                int x = q.top().second.first;
                int y = q.top().second.second;
                q.pop();
                int dxy[4] = {-1,0,1,0};
                rep (i,4) {
                    int nx = x + dxy[i];
                    int ny = y + dxy[(i+1)%4];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if (dist2[nx][ny] > d) {
                        dist2[nx][ny] = d;
                        q.push(make_pair(-d,make_pair(nx,ny)));
                    }
                }
            }
            rep (i,n) rep (j,m) if (a[i][j] == t)
                dist[i][j] = dist2[i][j];
        }
    }
    cout << dist[chest[p][0].first][chest[p][0].second] << endl;
    return 0;
}