[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;

}