记录编号	196424	评测结果	AAAAA
题目名称	[CTSC 1999] 拯救大兵瑞恩	最终得分	100
用户昵称	<蒟蒻>我要喝豆奶	是否通过	通过
代码语言	C++	运行时间	0.043 s
提交时间	2015-10-21 19:32:23	内存使用	12.40 MiB

#include<queue>
#include<cstdio>
#include<cstring>
#define MAXN 266UL
#define Ds 55UL
#define Es 1<<12
#define Null -1
using std::priority_queue;
int n,m,p,k,nodenum,s,Key[MAXN<<1][Ds],f[MAXN<<1][Es];
int Dr[MAXN][MAXN],num[Ds][Ds],edgenum,first[MAXN<<1];
struct Edge{int to,next;}edge[MAXN*MAXN];
struct Node{int keys,w,ver;inline friend bool operator<(Node a,Node b){return a.w>b.w;}};
priority_queue<Node>q;
inline void Add(int x,int y){edgenum++;edge[edgenum].to=y;edge[edgenum].next=first[x];first[x]=edgenum;}
inline int Hash(int i,int j){return num[i][j];}
int main(void){
	freopen("rescue.in","r",stdin);
	freopen("rescue.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&p,&k);
    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			num[i][j]=++nodenum;
    for(int i=1,x1,y1,x2,y2,kk;i<=k;i++){
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&kk);
        if(kk==0)
			Dr[Hash(x1,y1)][Hash(x2,y2)]=-1,Dr[Hash(x2,y2)][Hash(x1,y1)]=Null;
        else 
			Dr[Hash(x1,y1)][Hash(x2,y2)]=kk,Dr[Hash(x2,y2)][Hash(x1,y1)]=kk;
    }scanf("%d",&s);
	for(int i=1,x,y,kk;i<=s;i++){
		scanf("%d%d%d",&x,&y,&kk);
		Key[Hash(x,y)][++Key[Hash(x,y)][0]]=kk;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
        	if(j<m)
				if(Dr[Hash(i,j)][Hash(i,j+1)]!=Null)
					Add(Hash(i,j),Hash(i,j+1)),Add(Hash(i,j+1),Hash(i,j));
        	if(i<n)
				if(Dr[Hash(i,j)][Hash(i+1,j)]!=Null)
					Add(Hash(i,j),Hash(i+1,j)),Add(Hash(i+1,j),Hash(i,j));
    }memset(f,0x2f,sizeof f); 
	Node tp;
	tp.ver=Hash(1,1);
	for(int i=1;i<=Key[1][0];i++)
		tp.keys|=(1<<(Key[1][i]-1));
    tp.w=0;
	f[1][tp.keys]=0;
	q.push(tp);
    while(!q.empty()){
        Node fr=q.top();
		q.pop();
        if(fr.ver==num[n][m]){
            printf("%d",fr.w);
            return 0;
        }
        for(int i=first[fr.ver];i;i=edge[i].next){
            int K=Dr[fr.ver][edge[i].to];
            if(K){
                if(fr.keys&(1<<(K-1))){
                    tp.keys=0;
                    if(Key[edge[i].to][0])
                        for(int j=1;j<=Key[edge[i].to][0];j++)tp.keys|=1<<(Key[edge[i].to][j]-1);
                    tp.keys|=fr.keys;
                    if(f[edge[i].to][tp.keys]>fr.w+1){
                        f[edge[i].to][tp.keys]=fr.w+1;
                        tp.w=fr.w+1;tp.ver=edge[i].to;q.push(tp);
                    }
                }
            }
            else{
               tp.keys=0;
                if(Key[edge[i].to][0])
                    for(int j=1;j<=Key[edge[i].to][0];j++)tp.keys|=1<<(Key[edge[i].to][j]-1);
                tp.keys|=fr.keys;
                if(f[edge[i].to][tp.keys]>fr.w+1){
                    f[edge[i].to][tp.keys]=fr.w+1;
                    tp.w=fr.w+1;tp.ver=edge[i].to;q.push(tp);
                }
            }
        }
    }printf("-1");
	return 0;
}