题意分析

由题意可知，本题的难点1在于怎么对墙和门进行建边。2在于怎么处理钥匙和门之间的关系。
解答：对于门，可以直接进行建立边。墙，通过先将所有的加入集合，再进行。钥匙，可以看出钥匙的数量比较少，可以用二进制来进行表示。
之后，通过bfs来从左上角到右下角。不断的更新钥匙的状态和单位格，判断是否可以行走。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>
#include <set>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N=11,M=360,P=1<<10;
int n,m,k,p;
int h[N*N],e[M],w[M],ne[M],idx;
int g[N][N],key[N*N];
int dist[N*N][P];
bool st[N*N][P];
set<PII> edges;     

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,0,1,0},dy[4]={0,1,0,-1};
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        for(int u=0;u<4;u++)
        {
            int x=i+dx[u],y=j+dy[u];
            if(!x||x>n||!y||y>m)  continue;  //判断是否出界
            int a=g[i][j],b=g[x][y];
            if(!edges.count({a,b}))  add(a,b,0);    //如果在edges中存在{a,b}这个集合，那么进行建立边
        }
}
//双端队列  

int bfs()
{
    memset(dist,0x3f,sizeof dist);//初始化路径
    dist[1][0]=0;   //将当前点置为0，分别代表空格和钥匙的状态

    deque<PII> q;
    q.push_back({1,0});

    while(q.size())
    {
        PII t=q.front();//访问队头元素
        q.pop_front();//删除队头元素

        if(st[t.x][t.y])  continue;
        st[t.x][t.y]=true;  //标记

        if(t.x==n*m)  return dist[t.x][t.y];   //如果走到最后，直接返回

        if(key[t.x])
        {
            int state=t.y|key[t.x];     //更新钥匙的状态   或运算代表着各种钥匙是否存在，1代表存在，反之亦然。
            if(dist[t.x][state]>dist[t.x][t.y])
            {
                dist[t.x][state]=dist[t.x][t.y];    //当前单元格的钥匙状态
                q.push_front({t.x,state});          //加入队列
            }
        }

        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;      //步数
                q.push_back({j,t.y});   //插入队尾
            }
        }
    }
    return -1;//返回-1;
}

int main()
{
    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++;

    memset(h,-1,sizeof h);//初始化邻接表
    while(k--)
    {
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;  //输入点与点之间的关系
        int a=g[x1][y1],b=g[x2][y2];

        edges.insert({a,b}),edges.insert({b,a});   //加入集合edgs中
        if(c)  add(a,b,c),add(b,a,c);  //建立双向边
    }
    build();//预处理

    int s;
    cin>>s;   //钥匙
    while(s--)
    {
        int x,y,c;
        cin>>x>>y>>c;
        key[g[x][y]] |=1<<c-1;    //初始化每个钥匙所处的位置的状态
    }
    cout<<bfs()<<endl;
    return 0;
}