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]);
}
;
}