UTPC2012 : I - 最短路クエリ

さてここから300ptの問題。
ノーヒントで解くのが難しいので、ここからは解説読みながら解いてる。
http://utpc2012.contest.atcoder.jp/tasks/utpc2012_09

マス目ごとにコストが設定されている中で、最短路を求める。
特徴は、フィールドの幅Wが10と短く高さHが10000と細長いことと、答えるクエリ数Qが100000と多いこと。
当然真面目に毎回ダイクストラとかやっていては間に合わない。

そこで、フィールドを２分割して考える。この縦長のフィールドで、始点終点が真ん中より上と下に１つずつあるなら、必ず中間の高さの点を通るはず。
よって、中間の高さの位置にある幅W個分のマスについて、そこから全マスへの最短コストを計算しておく。
すると、始点からそのW個のいずれかを通って終点につくので、そのW個の各中間点について、始点～中間点＋中間点～終点－中間点のコストの最小値を取ればよい。

始点終点が中間点に対し同じ側にある場合は、再帰的に２分割したフィールドを再分割すればよい。
下記コードでは、逆に最少高さ10個から倍々に最大高さ10240個まで結合して中間点からの最小コストを求めている。

ところで、最初ダイクストラをQueueを使って書いたらTLEした。
同じところを何度も通ったのが原因。
本当はダイクストラはコスト最少のマスから隣接点を探すのに、今回は到達コストが更新されるたびにそのマスの隣接点を再度検索していた。
これに対処するには、隣接マスを未探索なマスについて、最小順に処理しないといけないんだけどそんなデータ構造あったかな…と思ったらmultimapがキーを最小順に並べていると知った。
これで無事解けるね。

int W,H,Q;
ll A[11][20001],TC[11][20001];
ll dist[11][11][11][20001]; // divlevel=10
ll inf=1LL<<50;
int loop;

void DFS(int sx,int sy,int miny, int maxy) {
	int x,y;
	multimap<ll,int> dfs;
	FOR(y,maxy-miny) FOR(x,W) TC[x][y+miny]=inf;
	
	TC[sx][sy]=A[sx][sy];
	dfs.insert(make_pair(TC[sx][sy], sy*100+sx));
	while(!dfs.empty()) {
		ll co=dfs.begin()->first;
		int key = dfs.begin()->second;
		dfs.erase(dfs.begin());
		int sx=key%100, sy=key/100;
		if(co>TC[sx][sy] || co>=inf) continue;
		int dx[4]={ 1,-1,0,0}, dy[4]={ 0,0,1,-1};
		FOR(loop,4) {
			int tx=sx+dx[loop];
			int ty=sy+dy[loop];
			if(tx<0 || tx>=W || ty<miny || ty>=maxy || ty>=H) continue;
			if(TC[tx][ty] > co+A[tx][ty]) dfs.insert(make_pair(TC[tx][ty] = co+A[tx][ty],ty*100+tx));
		}
	}
}

void solve() {
	int x,y,i,j,res,TM,nc;
	int tx,ty,ng,LS;
	char cmd[100];
	ll p,cch;
	
	GET3(&W,&H,&Q);
	FOR(i,sizeof(dist)/8) ((ll*)dist)[i]=inf;
	FOR(i,sizeof(A)/8) ((ll*)A)[i]=inf;
	FOR(y,H) FOR(x,W) A[x][y]=GETi();
	
	for(int level=0;level<11;level++) {
		int sh=10<<level;
		for(y=0;y<=H/sh;y++) {
			FOR(x,W) {
				DFS(x,y*sh+sh/2,y*sh,(y+1)*sh);
				FOR(ty,sh) FOR(tx,W) dist[level][x][tx][y*sh+ty]=TC[tx][y*sh+ty];
			}
		}
	}
	
	FOR(nc,Q) {
		int sx=GETi()-1;
		int sy=GETi()-1;
		int tx=GETi()-1;
		int ty=GETi()-1;
		ll cost=inf;
		
		if(sy>ty) swap(sx,tx), swap(sy,ty);
		if(sy/10 == ty/10) {
			DFS(sx,sy,sy/10*10,(sy/10+1)*10);
			cost = TC[tx][ty];
		}
		for(int level=0;level<11;level++) {
			int sh=10<<level;
			if(sy/sh == ty/sh) {
				FOR(i,W) {
					cost=min(cost,dist[level][i][sx][sy]+dist[level][i][tx][ty]-A[i][sy/sh*sh+sh/2]);
				}
			}
		}
		_P("%lld\n",cost);
	}
	
	return;
}

まとめ

探索空間を半々に分割するのと、multimapを使ったダイクストラ、２つの勉強になりました。