「重庆联考2017D2T2」密室 - 状态压缩+分层图 | Bill Yang's Blog

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

题目大意

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


题目分析

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

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


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#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;
}
姥爷们赏瓶冰阔落吧~
0%