5170 -- 【11.05题目】密室
Description
小 X 正困在一个密室里，他希望尽快逃出密室。 密室中有 N 个房间，初始时，小 X 在 1 号房间，而出口在 N 号房间。 密室的每一个房间中可能有着一些钥匙和一些传送门，一个传送门会单向地创造一条从房间 X 到房间 Y 的通道。另外，想要通过某个传送门，就必须具备一些种类的钥匙（每种钥匙都要有才能通过）。幸运的是，钥匙在打开传送门的封印后，并不会消失。 然而，通过密室的传送门需要耗费大量的时间，因此，小 X 希望通过尽可能少的传送门到达出口，你能告诉小 X 这个数值吗？ 另外，小 X 有可能不能逃出这个密室，如果是这样，请输出 "No Solution"。
Input
第一行三个整数 N,M,K，分别表示房间的数量、传送门的数量以及钥匙的种类数。 接下来 N 行，每行 K 个 0 或 1，若第 i 个数为 1，则表示该房间内有第 i 种钥匙，若第 i 个数为 0，则表示该房间内没有第 i 种钥匙。 接下来 M 行，每行先读入两个整数 X,Y，表示该传送门是建立在 X 号房间，通向 Y 号房间的，再读入 K 个 0 或 1，若第 i 个数为 1，则表示通过该传送门需要 i 种钥匙，若第 i 个数为 0，则表示通过该传送门不需要第 i 种钥匙。
Output
输出一行一个 “No Solution”，或一个整数，表示最少通过的传送门数。
Sample Input
3 3 2
1 0
0 1
0 0
1 3 1 1
1 2 1 0
2 3 1 1
Sample Output
2
Hint
直接记忆化每个点在某个状态的值可以强力剪枝，如果直接爆搜直接爆栈，最后加上DLZ的5000000运算次数以上就剪掉就过了。。。
code：
1 #include2 #include 3 #include 4 #include 5 #define N 100000 6 using namespace std; 7 int tot; 8 struct node { 9 long long u,v,w;10 } e[N];11 long long first[N],nxt[N],cnt,room[N];12 void add(long long u,long long v,long long w) {13 e[++cnt].u=u;14 e[cnt].v=v;15 e[cnt].w=w;16 nxt[cnt]=first[u];17 first[u]=cnt;18 }19 long long n,m,k;20 long long min0=20020731;21 int f[5001][2000];22 void dfs(long long x,long long now,long long step) {23 tot++;24 if(tot>=5000000)return;25 if(step>=min0)return;26 if(f[x][now]<=step)return;27 f[x][now]=step;28 if(x==n) {29 min0=min(min0,step);30 return;31 }32 for(long long i=first[x];i;i=nxt[i]){33 long long v=e[i].v;34 if((now&e[i].w)!=e[i].w)continue;35 long long temp=now|room[v];36 dfs(v,temp,step+1);37 if(tot>=5000000)return;38 }39 }40 long long read(){41 long long x=0,f=1;42 char c=getchar();43 while(!isdigit(c)){44 if(c=='-')f=-1;45 c=getchar();46 }47 while(isdigit(c)){48 x=(x<<3)+(x<<1)+c-'0';49 c=getchar();50 }51 return x*f;52 }53 int main() {54 int siz=80<<20;55 __asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(siz)+siz));56 n=read(),m=read(),k=read();57 for(long long i=1; i<=n; i++) {58 for(long long j=1; j<=k; j++) {59 long long x;60 x=read();61 room[i]=room[i]*2+x;62 }63 }64 for(long long i=1; i<=m; i++) {65 long long now=0;66 long long a,b;67 a=read(),b=read();68 for(long long j=1; j<=k; j++) {69 long long x;70 x=read();71 now=now*2+x;72 }73 add(a,b,now);74 }75 memset(f,0x3f3f3f3f,sizeof f);76 dfs(1,room[1],0);77 if(min0==20020731){78 cout<<"No Solution";79 }80 else{81 cout<
over