Golden Week Contest 2015 : D - 最短絡問題

本番これはすんなり思いつけた。
http://gwcontest2015.contest.atcoder.jp/tasks/gw2015_d

問題

H*Wのグリッドがある。
隣接セル間には扉があり、通るためにそれぞれ決まったコストがかかる。
ここで、あるセルから１つ右下のセルに移動する際、右・下と移動する場合(コストはA,D)と下・右(コストはC,B)と移動する場合、両経路の総コストは一致する(A+D=B+C)ことが分かっている。
また、A+C≦B+Dであることもわかっている。

このグリッドに対し、H*W回まで指定した２セル間の移動経路における最小コストを問い合わせることができる。
その情報をもとに、Q個のセルの対からなるクエリが与えられるので、それらの移動経路の最小コストを求めよ。

解法

H*Wは高々400なので、扉のコストをすべて求めてしまえば、Warshall-Floydで全セル対の最小移動コストを求められる。
あるセルに対し、右移動(A)と下移動(C)と右下移動(A+D=B+C)のコストが分かれば、残るB,Dのコストも求められる。

一番上の行の隣接セル間、及び一番左の隣接セル間について1回ずつクエリを投げて移動コストを求めよう。
あとは左上のセルから順に、AとCが確定したセルに対してA+D=B+Cを求めるクエリを投げ、順次B,Dを求めていこう。
実際は(H*W-1)回のクエリで十分である。

int H,W,Q;
int DH[20][20];
int DV[20][20];
ll mat[400][400];


int ask(int sy,int sx,int ty,int tx) {
	int i;
	_P("%d %d %d %d\n",sy+1,sx+1,ty+1,tx+1);
	fflush(stdout);
	scanf("%d",&i);
	return i;
}
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(x,400) FOR(y,400) mat[x][y]=1LL<<60;
	FOR(x,400) mat[x][x]=0;
	
	scanf("%d%d%d",&H,&W,&Q);
	FOR(y,H) FOR(x,W) {
		if(y==0 && x==0) ask(0,0,0,0);
		else if(y==0) mat[y*20+x-1][y*20+x]=mat[y*20+x][y*20+x-1]=ask(y,x,y,x-1);
		else if(x==0) mat[(y-1)*20+x][y*20+x]=mat[y*20+x][(y-1)*20+x]=ask(y,x,y-1,x);
		else {
			r=ask(y-1,x-1,y,x);
			mat[(y-1)*20+x][y*20+x]=mat[y*20+x][(y-1)*20+x]=r-mat[(y-1)*20+(x-1)][(y-1)*20+x];
			mat[y*20+(x-1)][y*20+x]=mat[y*20+x][y*20+(x-1)]=r-mat[(y-1)*20+(x-1)][y*20+(x-1)];
		}
	}
	FOR(i,400) FOR(x,400) FOR(y,400) mat[x][y]=min(mat[x][y],mat[x][i]+mat[i][y]);
	
	FOR(i,Q) {
		int sy,sx,ty,tx;
		scanf("%d%d%d%d",&sy,&sx,&ty,&tx);
		sy--,sx--,ty--,tx--;
		_P("%d\n",mat[sy*20+sx][ty*20+tx]);
		fflush(stdout);
	}
}

まとめ

A+C≦B+Dの条件の必要性がいまいちわかってない。