记录编号	234304	评测结果	AAAWAAAAAA
题目名称	[WC 1999]迷宫改造	最终得分	90
用户昵称	frontier	是否通过	未通过
代码语言	C++	运行时间	0.021 s
提交时间	2016-03-07 20:00:02	内存使用	1.15 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int g[22][22][22][22],d[22][22][3][3][3];
int dist[6][22][22];
bool inq[22][22][3][3][3],inque[22][22];
int nodex[6],nodey[6];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int n,m;
void pre(){
	queue<int>qx,qy;
	memset(dist,0x3f,sizeof(dist));
	for(int i=0;i<6;i++){
		qx.push(nodex[i]);qy.push(nodey[i]);
		dist[i][nodex[i]][nodey[i]]=0;
		while(!qx.empty()){
			int x=qx.front(),y=qy.front();qx.pop();qy.pop();
			inque[x][y]=0;
			for(int k=0;k<4;k++){
				int tx=x+dx[k],ty=y+dy[k];
				if(tx<1||tx>n||ty<1||ty>m||dist[i][tx][ty]<=dist[i][x][y]+g[x][y][tx][ty])continue;
				dist[i][tx][ty]=dist[i][x][y]+g[x][y][tx][ty];
				if(!inque[tx][ty])inque[tx][ty]=true,qx.push(tx),qy.push(ty);
			}
		}
	}
}
void spfa(){
	memset(d,0x3f,sizeof(d));
	queue<int>qx,qy,qa,qb,qc;
	qx.push(1);qy.push(1);qa.push(0);qb.push(0);qc.push(0);
	d[1][1][0][0][0]=0;
	while(!qx.empty()){
		int x=qx.front(),y=qy.front(),a=qa.front(),b=qb.front(),c=qc.front();
		qx.pop();qy.pop();qa.pop();qb.pop();qc.pop();
		inq[x][y][a][b][c]=0;
		for(int i=0;i<4;i++){
			int tx=x+dx[i],ty=y+dy[i];
			if(tx<1||tx>n||ty<1||ty>m)continue;
			int cost=a==1||b==1||c==1?g[x][y][tx][ty]:0;
			if(d[tx][ty][a][b][c]>d[x][y][a][b][c]+cost){
				d[tx][ty][a][b][c]=d[x][y][a][b][c]+cost;
				if(!inq[tx][ty][a][b][c]){
					inq[tx][ty][a][b][c]=1;
					qx.push(tx);qy.push(ty);qa.push(a);qb.push(b);qc.push(c);
				}
			}
		}
		if(a<2){
			if(d[x][y][a+1][b][c]>d[x][y][a][b][c]+dist[a][x][y]){
				d[x][y][a+1][b][c]=d[x][y][a][b][c]+dist[a][x][y];
				if(!inq[x][y][a+1][b][c]){
					inq[x][y][a+1][b][c]=1;
					qx.push(x);qy.push(y);qa.push(a+1);qb.push(b);qc.push(c);
				}
			}
		}
		if(b<2){
			if(d[x][y][a][b+1][c]>d[x][y][a][b][c]+dist[b+2][x][y]){
				d[x][y][a][b+1][c]=d[x][y][a][b][c]+dist[b+2][x][y];
				if(!inq[x][y][a][b+1][c]){
					inq[x][y][a][b+1][c]=1;
					qx.push(x);qy.push(y);qa.push(a);qb.push(b+1);qc.push(c);
				}
			}
		}
		if(c<2){
			if(d[x][y][a][b][c+1]>d[x][y][a][b][c]+dist[c+4][x][y]){
				d[x][y][a][b][c+1]=d[x][y][a][b][c]+dist[c+4][x][y];
				if(!inq[x][y][a][b][c+1]){
					inq[x][y][a][b][c+1]=1;
					qx.push(x);qy.push(y);qa.push(a);qb.push(b);qc.push(c+1);
				}
			}
		}
	}
}
int main(){
	freopen("rebuildmaze.in","r",stdin);
	freopen("rebuildmaze.out","w",stdout); 
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	for(int k=0;k<4;k++){
		int x=i+dx[k],y=j+dy[k];
		if(x<1||x>n||y<1||y>m)continue;
		g[i][j][x][y]=1;
	}
	int k;scanf("%d",&k);
	int x1,x2,y1,y2,ans=k;
	while(k--){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		g[x1][y1][x2][y2]=g[x2][y2][x1][y1]=0;
	}
	scanf("%d",&k);
	for(int i=0;i<k;i++)
	for(int j=0;j<2;j++)
	scanf("%d%d",&nodex[i*2+j],&nodey[i*2+j]);
	for(int i=k;i<3;i++)
	for(int j=0;j<2;j++)
	nodex[i*2+j]=nodex[j],nodey[i*2+j]=nodey[j];
	pre();
	spfa();
	int tot=1e9;
	for(int i=0;i<3;i+=2)
	for(int j=0;j<3;j+=2)
	for(k=0;k<3;k+=2){
		int cost=0;
		if(!i)cost+=dist[0][nodex[1]][nodey[1]];
		if(!j)cost+=dist[2][nodex[3]][nodey[3]];
		if(!k)cost+=dist[4][nodex[5]][nodey[5]];
		tot=min(tot,d[n][m][i][j][k]+cost);
	}
	printf("%d\n",tot);
	return 0;
}