1131. 拯救大兵瑞恩

解题思路：题目大意是要到一个位置，但是图中会有对应的门，而且门的种类不同，需要不同种钥匙来打开，不同种的钥匙分别放在地图中的某个位置，问最多要多少步才能到。
这道题的解题思路也是非常的取巧，他并没有告诉你每个点之间的边，这个需要我们去构造，并且还有墙，墙是不可逾越的，那么我们需要用一个set来维护两条边之间是否存在墙或者门，我们初始的dist一维数组是肯定不够的，要开第二个状态[j],这里的状态应该用个二进制状态来存，如果开始搜的时候两点之间的w[i]如果大于0，那么二进制状态右移w[i]位&1如果等于0那么就不存在。在采用bfs的时候，如果脚下有钥匙我们肯定要捡起，然后双端队列的可以做到优化的效果，把捡钥匙的放在队头，不捡的放在队尾。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<deque>
#include<set>
using namespace std;
const   int N = 11 ,M=N*N*4 ,P = 1<<10;
#define x first
#define y second
typedef pair<int ,int> PII;
set<PII>S;
int e[M],ne[M],h[M],w[M];
int dist[M][P];
bool st[M][P];
int g[N][N];
int key[M];
int idx ;
int n , m , p ,s , k ;
void add(int a,int b,int c)
{
   
    e[idx] =  b, w[idx] = c ,ne[idx] = h[a], h[a] = idx++; 
}
void build()
{
   
    int dx[4] ={
   1,-1,0,0},dy[4]={
   0,0,1,-1};
    for(int i=1; i<=n;i++)
    for(int j = 1;j<=m;j++)
    for(int k=0;k<4;k++)
    {
   
        int tx=i+dx[k];
        int  ty=j+dy[k];
        if(!tx||!ty||tx>n||ty>m)    continue;
        if(S.count({
   g[tx][ty],g[i][j]}))    continue;
        add(g[tx][ty],g[i][j],0),add(g[i][j],g[tx][ty],0);
    }
}
int bfs()
{
   
    deque<PII>q;
    memset(dist,0x3f,sizeof dist);
    dist[1][0]=0;
    st[1][0]=true;
    q.push_back({
   1,0});
    while(q.size())
    {
   
        PII t= q.front();
        q.pop_front();
        if(t.x==n*m)
        return dist[t.x][t.y];
        if(key[t.x])
        {
   
            int ss =t.y|key[t.x];
            if(dist[t.x][ss]>dist[t.x][t.y])
            {
   
                dist[t.x][ss]=dist[t.x][t.y];
                st[t.x][ss]=true;
                q.push_front({
   t.x,ss});
            }
        }
        for(int i=h[t.x];~i;i=ne[i])
        {
   
            int j=e[i];
            if(w[i]&&!(t.y>>w[i]-1&1))  continue;
            if(dist[j][t.y]>dist[t.x][t.y]+1)
            {
   
                dist[j][t.y]=dist[t.x][t.y] +1;
                if(!st[j][t.y])
            {
   
                st[j][t.y]=true;
                q.push_back({
   j,t.y});
            }
            }
        }
    }
    return -1;
}
int main()
{
   
    memset(h,-1,sizeof h);
    cin >>  n >> m >> p >> k;
    for(int i = 1,t=1 ;i <= n   ; i++)
    for(int j = 1; j<= m; j++)
    g[i][j] =  t++;
    while(k--)
    {
   
        int x1 ,y1, x2 ,y2 ,G;
        cin >> x1 >> y1 >> x2 >> y2 >> G;
        int a = g[x1][y1] , b =  g[x2][y2];
        if(G)   add(a,b,G),add(b,a,G);
        S.insert({
   a,b}),S.insert({
   b,a});
    }
    build();
    cin >>  s;
    while(s--)
    {
   
        int x1,y1,t;
        cin >> x1 >> y1 >> t;
        int loc = g[x1][y1];
        key[loc] |= 1<< t -1 ;
    }
    cout << bfs() << endl;
    return 0;
}