记录编号	196488	评测结果	AAAAA
题目名称	[CTSC 1999] 拯救大兵瑞恩	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2015-10-21 20:13:38	内存使用	11.57 MiB

#include<cstdio>
#include<cstring>

using namespace std;

const int MAXN=20;
const int MAXM=300000;
const int gx[4]={-1,0,1,0};
const int gy[4]={0,1,0,-1};
const int INF=0x3fffffff;

bool vis[MAXM];

int n,m,p,k,s,tot,h[MAXM],Pow[MAXN],map[MAXN][MAXN][MAXN][MAXN],dis[MAXM],q[MAXM<<2],head,tail,Ans;

struct Edge{
	int v,w,next;
}e[MAXM];

struct key{
	int a[15];
}c[1500];

inline int Min(int a,int b) {
	return a<b?a:b;
}
 
inline void add(int u,int v,int w) {
	e[++tot].v=v;
	e[tot].w=w;
	e[tot].next=h[u];
	h[u]=tot;
}

inline void change(int x) {
	int t=x;
	memset(c[x].a,0,sizeof(c[x].a));
	while(t){
		c[x].a[++c[x].a[0]]=t%2;
		t/=2;
	}
}

inline int Get(int x,int y) {
	int res=0;
	for(int i=1;i<=p;++i) {
		if(i==y) res+=Pow[i-1]*(c[x].a[i]==0?1:0);
		else res+=Pow[i-1]*c[x].a[i];
	}
	return res;
}

inline void spfa(int x) {
	head=1,tail=1;
	for(int i=0;i<MAXM;++i) dis[i]=INF;
	q[head]=x,dis[x]=0,vis[x]=1;
	while(head<=tail) {
		int u=q[head];
		vis[u]=0;
		head++;
		for(int i=h[u];i;i=e[i].next) {
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].w) {
				dis[v]=dis[u]+e[i].w;
				if(!vis[v]) {
					q[++tail]=v;
					vis[v]=1;
				}
			}
		}
	}
}

inline void init(){
	Pow[0]=1;memset(map,128,sizeof(map));
	scanf("%d%d%d%d",&n,&m,&p,&k);
	for(int i=1;i<=p;++i) Pow[i]=Pow[i-1]*2;
	for(int i=1,X1,X2,Y1,Y2,Z;i<=k;++i) {
		scanf("%d%d%d%d%d",&X1,&Y1,&X2,&Y2,&Z);
		map[X1][Y1][X2][Y2]=map[X2][Y2][X1][Y1]=Z;
	}
	memset(c[0].a,0,sizeof(c[0].a));
	for(int i=1;i<=Pow[p];++i) change(i);
	scanf("%d",&s);
	for(int i=1,x,y,z;i<=s;++i) {
		scanf("%d%d%d",&x,&y,&z);
		for(int j=0;j<Pow[p];++j) {
			if(!c[j].a[z]) {
				int t=Get(j,z);
				add((x-1)*m+y+j*n*m,(x-1)*m+y+t*n*m,0);
			}
		}
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			for(int k=0;k<4;++k) {
				int x=i+gx[k],y=j+gy[k];
				if(x>0&&x<=n&&y>0&&y<=m) {
					if(map[i][j][x][y]<0) {
						for(int l=0;l<Pow[p];++l) {
							add((i-1)*m+j+l*n*m,(x-1)*m+y+l*n*m,1);
						}
					}
					if(map[i][j][x][y]>=1) {
						for(int l=0;l<Pow[p];++l) {
							if(c[l].a[map[i][j][x][y]]) {
								add((i-1)*m+j+l*n*m,(x-1)*m+y+l*n*m,1);
							}
						}
					}
				}
			}
		}
	}
	Ans=INF;
	spfa(1);
	for(int i=1;i<=Pow[p];++i) {
		Ans=Min(Ans,dis[n*m*i]);
	}
	if(Ans==INF) printf("-1");
	else printf("%d",Ans);
}

int main(){
	freopen("rescue.in","r",stdin);
	freopen("rescue.out","w",stdout);
	init();
	return 0;
}