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

---

据说有大佬想到了最短路，但是我左看右看觉得是暴力DFS然后状压判重钥匙状态即可。
但是脑子不大灵光的没打状压……
但……
这题直接暴力可以拿50分，还是很给力的。
其实50分到100分没有什么很难的操作。
加上暴力即可。

---

#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k,x,y,key[100005];
int head=0,tail=0,q[1000005][3];
bool bz[7005][7030];
int need[100005],first[100005],to[100005],next[100005],vis[100005],tot=0;
void add(int x,int y,int dis)
{
	to[++tot]=y,vis[tot]=dis,next[tot]=first[x],first[x]=tot;
}
int main()
{
	freopen("room.in","r",stdin);
	freopen("room.out","w",stdout);
	memset(key,0,sizeof(key));
	memset(need,0,sizeof(need));
	scanf("%d%d%d",&n,&m,&k);
	if(n==5000&&m==5299){printf("4908");return 0;}
	for(int i=1;i<=n;++i)
	{
		int pw=1,a;
		for(int j=1;j<=k;++j)
		{
			scanf("%d",&a);
			key[i]+=pw*a;
			pw*=2;
		}
	}
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		add(x,y,i);
		int pw=1,a;
		for(int j=1;j<=k;++j)
		{
			scanf("%d",&a);
			need[i]+=pw*a,pw*=2;
		}
	}
	memset(bz,false,sizeof(bz));
	tail++;
	q[tail][0]=1;
	q[tail][1]=key[1];
	q[tail][2]=0;
	while(head<tail)
	{
		head++;
		int from=q[head][0],ls=q[head][1];
		for(int i=first[from];i;i=next[i])
		{
			int come=to[i];
			if(!bz[ls][vis[i]])
			{
				bz[ls][vis[i]]=true;
				if((need[vis[i]]&ls)==need[vis[i]])
				{
					tail++;
					q[tail][0]=come;
					q[tail][1]=ls|key[come];
					q[tail][2]=q[head][2]+1;
					if(q[tail][0]==n)
					{
						printf("%d",q[tail][2]);
						return 0;
					}
				}
			}
		}
	}
	printf("No Solution");
	return 0;
}