https://nanti.jisuanke.com/t/17323
小 X 正困在一个密室里,他希望尽快逃出密室。
密室中有 N 个房间,初始时,小 X 在 1号房间,而出口在 N号房间。
密室的每一个房间中可能有着一些钥匙和一些传送门,一个传送门会单向地创造一条从房间 X 到房间 Y 的通道。另外,想要通过某个传送门,就必须具备一些种类的钥匙(每种钥匙都要有才能通过)。幸运的是,钥匙在打开传送门的封印后,并不会消失。
然而,通过密室的传送门需要耗费大量的时间,因此,小 X 希望通过尽可能少的传送门到达出口,你能告诉小 X 这个数值吗?
另外,小 X 有可能不能逃出这个密室,如果是这样,请输出 "No Solution"
。
输入格式
第一行三个整数 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种钥匙。
输出格式
输出一行一个 "No Solution"
,或一个整数,表示最少通过的传送门数。
思路:
一道很有意思的搜索题,如果没有钥匙存在的话,那么这道题就变成一道纯粹的搜索题了。
在有钥匙存在的情况下,那么思考用什么来表示钥匙的状态最为方便。。。那显然是二进制了,每一次钥匙状态的判断可以用与运算解决,钥匙的传递可以用或运算解决,非常方便而且复杂度极低。
具体看代码以及最后一组测试点没有过(大雾
代码:
#include <stdio.h> #include <string.h> #include <queue> #include <vector> using namespace std; ]; ]; ]; int n,m,k; struct edge { int from,to; int cost; }; vector<edge> edges; vector<]; void adde(int from,edge tmp) { edges.push_back(tmp); int m = edges.size(); v[); } void bfs1(void) { vis[] = ; queue<int> q; q.push(); ; while (!q.empty()) { int s = q.front();q.pop(); ;i < v[s].size();i++) { int j = v[s][i]; int to = edges[j].to; if (vis[to]) continue; vis[to] = ; dis[to] = dis[s] + ; q.push(to); if (to == n) { f = ; break; } } if (f) break; } } void bfs2() { vis[] = ; queue<int> q; q.push(); ; while (!q.empty()) { int s = q.front();q.pop(); ;i < v[s].size();i++) { int j = v[s][i]; int to = edges[j].to; int w = edges[j].cost; if (vis[to]) continue; if ((key[s] & w) < w) continue; key[to] |= w; key[to] |= key[s]; vis[to] = ; dis[to] = dis[s] + ; q.push(to); if (to == n) { f = ; break; } } if (f) break; } } int main() { scanf("%d%d%d",&n,&m,&k); if (!k) { ;i < m;i++) { int x,y; scanf("%d%d",&x,&y); edge tmp = (edge){x,y,}; adde(x,tmp); } bfs1(); if (!vis[n]) printf("No Solution\n"); else printf("%d\n",dis[n]); } else { ;i <= n;i++) { ; ;j <= k;j++) { int x; scanf("%d",&x); << j); } key[i] = tmp; } ;i <= m;i++) { int x,y; scanf("%d%d",&x,&y); ; ;j <= k;j++) { int x; scanf("%d",&x); << j); } edge e = (edge){x,y,tmp}; adde(x,e); } bfs2(); if (!vis[n]) printf("No Solution\n"); else printf("%d\n",dis[n]); } ; }