「重庆联考2017D2T2」密室 - 状态压缩+分层图

题目大意

    小X正困在一个密室里，他希望尽快逃出密室。
    密室中有$N$个房间，初始时，小X在$1$号房间，而出口在$N$号房间。
    密室的每一个房间中可能有着一些钥匙和一些传送门，一个传送门会单向地创造一条从房间X到房间Y的通道。另外，想要通过某个传送门，就必须具备一些种类的钥匙（每种钥匙都要有才能通过）。幸运的是，钥匙在打开传送门的封印后，并不会消失。
    然而，通过密室的传送门需要耗费大量的时间，因此，小X希望通过尽可能少的传送门到达出口，你能告诉小X这个数值吗？
    另外，小X有可能不能逃出这个密室，如果是这样，请输出No Solution。

---

题目分析

$K\le10$明显可以对钥匙进行状压。
$f[i,S]$表示到达点$i$，当前钥匙拥有情况为$S$的最少次数。

接下来用Bfs更新最短路即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

#define pii pair<int,int>
#define mp make_pair

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

struct Edge {
	int from,to,need;
};

const int maxn=5005,maxk=1024;
vector<Edge>edges[maxn];
int dist[maxn][maxk],a[maxn];
bool vst[maxn][maxk]; 

void AddEdge(int x,int y,int v) {
	edges[x].push_back((Edge) {
		x,y,v
	});
}

void Bfs() {
	queue<pii>Q;
	Q.push(mp(1,a[1]));
	vst[1][a[1]]=1;
	while(!Q.empty()) {
		pii Now=Q.front();
		Q.pop();
		for(int i=0; i<edges[Now.first].size(); i++) {
			Edge& e=edges[Now.first][i];
			int Next=e.to,Nexts=Now.second|a[Next];
			if(((Now.second&e.need)!=e.need)||vst[Next][Nexts])continue;
			vst[Next][Nexts]=1;
			dist[Next][Nexts]=dist[Now.first][Now.second]+1;
			Q.push(mp(Next,Nexts));
		}
	}
}

int n,m,K;

int main() {
	n=Get_Int();
	m=Get_Int();
	K=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=0; j<K; j++)a[i]|=(Get_Int())<<j;
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),y=Get_Int(),v=0;
		for(int j=0; j<K; j++)v|=(Get_Int())<<j;
		AddEdge(x,y,v);
	}
	Bfs();
	int ans=0x7fffffff/2;
	for(int i=0; i<(1<<K); i++)
		if(vst[n][i])ans=min(ans,dist[n][i]);
	if(ans==0x7fffffff/2)puts("No Solution");
	else printf("%d\n",ans);
	return 0;
}