【状态压缩 搜索】SSL_1150 密室

本文主要是介绍【状态压缩 搜索】SSL_1150 密室，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

有$N$个房间， $M$个传送门，$K$种钥匙，每个房间有一些钥匙，每个传送门可以从一个房间传到另一个房间，需要一定的钥匙才能使用传送门，求出经过最少的传送门能从$1$号房间到达$N$号房间。

思路

压缩钥匙的状态，然后$BFS$就行了。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;struct node{int to, k, next;
}e[6001];
struct state{int w, k;
};
int N, M, K, ans, x;
int key[5001], list[5001], d[2048][5001];void bfs() {queue<state> q;q.push((state){1, key[1]});memset(d, -1, sizeof(d));d[key[1]][1] = 0;while (q.size()) {state head = q.front();q.pop();for (int i = list[head.w]; i; i = e[i].next) {int s = head.k, y = e[i].to;if ((s & e[i].k) == e[i].k && d[s | key[y]][y] == -1) {//判断分层q.push((state){y, s | key[y]});d[s | key[y]][y] = d[s][head.w] + 1;}}if (head.w == N) ans = min(ans, d[head.k][N]);}
}int main() {scanf("%d %d %d", &N, &M, &K);for (int i = 1; i <= N; i++) {for (int j = 1; j <= K; j++) {scanf("%d", &x);key[i] = key[i] << 1 | x;}}for (int i = 1; i <= M; i++) {scanf("%d %d", &x, &e[i].to);e[i].next = list[x];list[x] = i;for (int j = 1; j <= K; j++) {scanf("%d", &x);e[i].k = e[i].k << 1 | x;}}ans = 2147483647;bfs();if (ans == 2147483647) printf("No Solution");else printf("%d", ans);
}

这篇关于【状态压缩 搜索】SSL_1150 密室的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---