[solution] JZOJ 5459. 密室
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
Data Constraint
$n\leq5000,m\leq6000,k\leq10$
分割线
想法
最短路？BFS？
看到传送门，钥匙，还不消失，还有$k\leq10$，是不是感觉很亲切。对这里需要一个状压。
其实就是一个带状压的BFS
想到这里这个题就不难了，在正常BFS过程中加上状压代码和可行性判断（就是钥匙是否足够），OK成功AC掉这个题
Code
78ms,20.59MB
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,k;
int book[5003][1050];
struct Edge{
int s,t,nxt,w;
}edge[6003];
int head[5003],tot=0;
int ky[5003];
queue<pair<int,int> > q;
void add(){
int st,to,we=0;scanf("%d %d",&st,&to);
for(int i=1;i<=k;i++){int p;scanf("%d",&p);we*=2;we+=p;}
edge[tot].s=st;
edge[tot].t=to;
edge[tot].nxt=head[st];
edge[tot].w=we;
head[st]=tot;
tot++;
}
void bfs(){
q.push(make_pair(1,0));
book[1][0]=1;
while(!q.empty()){
int np=q.front().first,nw=q.front().second;
nw|=ky[np];
for(int i=head[np];i!=-1;i=edge[i].nxt)
if((int)(edge[i].w & nw)==edge[i].w)
if(book[edge[i].t][nw]==-1)
if(edge[i].t==n){
printf("%d\n",book[np][q.front().second]);return;
}
else{
q.push(make_pair(edge[i].t,nw));
book[edge[i].t][nw]=book[np][q.front().second]+1;
}
q.pop();
}
printf("No Solution\n");return;
}
void init(){
memset(book,-1,sizeof(book));
memset(ky,0,sizeof(ky));
memset(head,-1,sizeof(head));
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++){
int p;scanf("%d",&p);
ky[i]<<=1;
ky[i]|=p;
}
for(int i=1;i<=m;i++)
add();
}
int main(){
freopen("room.in","r",stdin);
freopen("room.out","w",stdout);
init();
bfs();
return 0;
}