记录编号	153928	评测结果	AAAAA
题目名称	[CTSC 1999] 拯救大兵瑞恩	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-03-20 12:08:10	内存使用	4.21 MiB

#include<iostream>
#include<cstdio>
using namespace std;
const int INF=1e9;

int n,m,C,k,g,s,i,j,p,zj1,zj2,zj3,x,x1,x2,y,y1,y2,z,ans;
/*---------------------------------------------------------------*/
int quex[231000]={0},quey[231000]={0},quez[231000]={0};
bool flag[1025][16][16]={0};int qhead=1,qtail=230999,qnum=0;
inline void GET()
{
	x=quex[qhead],y=quey[qhead],z=quez[qhead];
	if(++qhead==231000)qhead=1;
	qnum--;flag[z][x][y]=0;
}
inline void PUSH_fr(int X,int Y,int Z)
{
	flag[Z][X][Y]=1,qnum++;
	if(!(--qhead))qhead=230999;
	quex[qhead]=X,quey[qhead]=Y,quez[qhead]=Z;
}
inline void PUSH_be(int X,int Y,int Z)
{
	flag[Z][X][Y]=1,qnum++;
	if(++qtail==231000)qtail=1;
	quex[qtail]=X,quey[qtail]=Y,quez[qtail]=Z;
}
/*---------------------------------------------------------------*/

int upedge[16][16]={0},riedge[16][16]={0},key[16][16]={0};
void init()
{
	scanf("%d%d%d",&n,&m,&C);
	scanf("%d",&k);
	for(i=1;i<=k;i++)
	{
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g);
		if(x1==x2)
		{
			if(y1>y2)y1=y2;
			if(g)riedge[x1][y1]|=(1<<(g-1));
			else riedge[x1][y1]=-1;
		}
		else if(y1==y2)
		{
			if(x1<x2)x1=x2;
			if(g)upedge[x1][y1]|=(1<<(g-1));
			else upedge[x1][y1]=-1;
		}
	}
	scanf("%d",&s);
	for(i=1;i<=s;i++)
	{
		scanf("%d%d%d",&x1,&y1,&g);g--;
		key[x1][y1]|=(1<<g);
	}
}

int dis[1025][16][16]={0};
void spfa()
{
	zj1=1<<C;
	for(i=0;i<=zj1;i++)for(p=1;p<=n;p++)
	for(j=1;j<=m;j++)dis[i][p][j]=INF;
	dis[0][1][1]=0;PUSH_be(1,1,0);
	while(qnum)
	{
		GET();zj1=z|key[x][y];
		if(x>1)if(dis[zj1][x-1][y]>dis[z][x][y]+1)
		if((upedge[x][y]!=-1)&&(upedge[x][y]==(zj1&upedge[x][y])))
		{
			dis[zj1][x-1][y]=dis[z][x][y]+1;if(!flag[zj1][x-1][y])
			if(qnum&&dis[quez[qhead]][quex[qhead]][quey[qhead]]>=dis[zj1][x-1][y])
			PUSH_fr(x-1,y,zj1);else PUSH_be(x-1,y,zj1);
		}
		
		if(x<n)if(dis[zj1][x+1][y]>dis[z][x][y]+1)
		if((upedge[x+1][y]!=-1)&&(upedge[x+1][y]==(zj1&upedge[x+1][y])))
		{
			dis[zj1][x+1][y]=dis[z][x][y]+1;if(!flag[zj1][x+1][y])
			if(qnum&&dis[quez[qhead]][quex[qhead]][quey[qhead]]>=dis[zj1][x+1][y])
			PUSH_fr(x+1,y,zj1);else PUSH_be(x+1,y,zj1);
		}
		
		if(y>1)if(dis[zj1][x][y-1]>dis[z][x][y]+1)
		if((riedge[x][y-1]!=-1)&&(riedge[x][y-1]==(zj1&riedge[x][y-1])))
		{
			dis[zj1][x][y-1]=dis[z][x][y]+1;if(!flag[zj1][x][y-1])
			if(qnum&&dis[quez[qhead]][quex[qhead]][quey[qhead]]>=dis[zj1][x][y-1])
			PUSH_fr(x,y-1,zj1);else PUSH_be(x,y-1,zj1);
		}
		
		if(y<m)if(dis[zj1][x][y+1]>dis[z][x][y]+1)
		if((riedge[x][y]!=-1)&&(riedge[x][y]==(zj1&riedge[x][y])))
		{
			dis[zj1][x][y+1]=dis[z][x][y]+1;if(!flag[zj1][x][y+1])
			if(qnum&&dis[quez[qhead]][quex[qhead]][quey[qhead]]>=dis[zj1][x][y+1])
			PUSH_fr(x,y+1,zj1);else PUSH_be(x,y+1,zj1);
		}
	}
	ans=INF;zj1=1<<C;
	for(i=0;i<=zj1;i++)
	if(ans>dis[i][n][m])ans=dis[i][n][m];
	if(ans==INF)ans=-1;
}
int main()
{
	freopen("rescue.in","r",stdin);
	freopen("rescue.out","w",stdout);
	init();
	spfa();
	printf("%d\n",ans);
	return 0;
}