记录编号	236887	评测结果	AAAAA
题目名称	[CTSC 1999] 拯救大兵瑞恩	最终得分	100
用户昵称	6+1	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2016-03-15 19:36:08	内存使用	29.91 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define inf 0x3ffffff
const int N=300000;
int n,m,p,K,S,ans,tot=1,point[N],next[N*5],dis[N],l[1000000];
int map[16][16][16][16],key[16][16][11],pow[2000];
int xi[4]={-1,0,0,1},yi[4]={0,-1,1,0};
struct A{int st,en,va;}aa[N*5];
struct C{int a[11];}c[1200];
bool f[N];
void add(int x,int y,int z)
{
    tot++;next[tot]=point[x];point[x]=tot;
    aa[tot].st=x;aa[tot].en=y;aa[tot].va=z;
}
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;
    }
}
int get_line(int x,int y)
{
    int i,out=0;
    for(i=1;i<=p;++i){
        if(i==y) out+=pow[i-1]*(c[x].a[i]==0?1:0);
        else out+=pow[i-1]*c[x].a[i];
    }
    return out;
}
void SPFA(int x)
{
    int i,u,h=1,t=1;
    memset(f,1,sizeof(f));
    memset(dis,127/3,sizeof(dis));
    l[h]=x;dis[x]=0;
    while(h<=t){
        u=l[h];
        f[u]=true;
        for(i=point[u];i;i=next[i])
          if(dis[aa[i].en]>dis[u]+aa[i].va){
            dis[aa[i].en]=dis[u]+aa[i].va;
            if(f[aa[i].en]){
                f[aa[i].en]=false;
                t+=1;
                l[t]=aa[i].en;
            }
          }
          h+=1;
    }
}
int main()
{
    freopen("rescue.in","r",stdin);
    freopen("rescue.out","w",stdout);
    int i,j,k,l,x1,y1,x2,y2,x,y,z;
    scanf("%d%d%d%d",&n,&m,&p,&K);
    memset(map,128,sizeof(map));
    pow[0]=1;
    for(i=1;i<=10;++i) pow[i]=pow[i-1]*2;
    for(i=1;i<=pow[p];++i) change(i);
    memset(c[0].a,0,sizeof(c[0].a));
    for(i=1;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;
    }
    scanf("%d",&S);
    for(i=1;i<=S;++i){
        scanf("%d%d%d",&x,&y,&z);
        for(j=0;j<pow[p];++j)
          if(!c[j].a[z]){
            int t=get_line(j,z);
            add((x-1)*m+y+j*n*m,(x-1)*m+y+t*n*m,0);
          }
    }
    for(i=1;i<=n;++i)
      for(j=1;j<=m;++j)
        for(k=0;k<=3;++k){
            x=i+xi[k];y=j+yi[k];
            if(x>0&&x<=n&&y>0&&y<=m){
                if(map[i][j][x][y]<0)
                  for(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(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(i=1;i<=pow[p];++i)
      ans=min(ans,dis[n*m*i]);
    ans=(ans==inf?-1:ans);
    printf("%d\n",ans);
}