记录编号	210847	评测结果	AAAAA
题目名称	[CTSC 1999] 拯救大兵瑞恩	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2015-11-29 11:20:59	内存使用	15.55 MiB

#include<cstdio>
#include<cstring>
int N,M,P,K;
int a[4]={0,0,1,-1},b[4]={1,-1,0,0};
int d[2100][20][20];
int o[20][20][20][20];
int flag[20][20];
void clear()
{
	memset(o,-1,sizeof(o));
	memset(d,0x3f,sizeof(d));
}
int x,y,u,v,g,s,tip;
void init()
{
	clear();
	scanf("%d%d%d",&N,&M,&P);
	scanf("%d",&K);
	for(int i=0;i<K;++i)
	{
		scanf("%d%d%d%d",&x,&y,&u,&v);
		scanf("%d",&o[x][y][u][v]);
		o[u][v][x][y]=o[x][y][u][v];
	}
	scanf("%d",&s);
	for(int i=0;i<s;++i)
	{
		scanf("%d%d",&x,&y);
		scanf("%d",&tip);
		if(tip)
			flag[x][y]|=1<<tip;
	}
}
struct que
{
	int now,x,y;
}q[1000100];
int l,r,now;
void spfa()
{
	q[0].x=1;
	q[0].y=1;
	if(flag[1][1])
		q[0].now=1<<flag[1][1];
	d[q[0].now][1][1]=0;
	while(l<=r)
	{
		x=q[l].x;
		y=q[l].y;
		now=q[l++].now;
		for(int i=0;i<4;++i)
		{
			u=x+a[i];
			v=y+b[i];
			if(u&&v&&u<=N&&v<=M&&(o[x][y][u][v]<0||now&(1<<o[x][y][u][v])))
			{
				if(d[now][u][v]>d[now][x][y]+1)
				{
					d[now][u][v]=d[now][x][y]+1;
					q[++r].x=u;
					q[r].y=v;
					q[r].now=now;
					if(flag[u][v])
					{
						d[now|flag[u][v]][u][v]=d[now][x][y]+1;
						q[r].now|=flag[u][v];
					}
				}
			}
		}
	}
}
int main()
{
	freopen("rescue.in","r",stdin);
	freopen("rescue.out","w",stdout);
	init();
	spfa();
	int ans=0x7fffffff;
	for(int i=0;i<2050;++i)
		if(d[i][N][M]<ans)
		    ans=d[i][N][M];
	if(ans>1e6)
	    puts("-1");
	else
	    printf("%d",ans);
	getchar();
	getchar();
	getchar();
	getchar();
}