用优先队列来储存每一个点距离起点的距离，需要注意的是一个点可能有多个钥匙，因此key数组初始化时要用异或而不是直接赋值

CODE

#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+100;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const double eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
typedef pair<int,int> pii;
struct node{
    int x1,y1,x2,y2;
};
struct Node{
    int x,y,d,z;
    bool operator<(const Node &o) const{
        return d>o.d;
    }
};
int n,m,k,p,s;
int Next[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int key[11][11];
map<pair<pii,pii>,int> wal,dor;
bool vis[20][20][1<<10];
priority_queue<Node> q;
int bfs(int x,int y){
    int tmp=0;
    if(key[x][y]) tmp=key[x][y];
    q.push({x,y,0,tmp});
    while(!q.empty()){
        Node fr=q.top();
        q.pop();
        if(fr.x==n && fr.y==m) return fr.d;
        if(vis[fr.x][fr.y][fr.z]) continue;
        vis[fr.x][fr.y][fr.z]=1;
        for(int i=0;i<4;i++){
            int nx=fr.x+Next[i][0];
            int ny=fr.y+Next[i][1];
            if(nx<1 || nx>n || ny<1 || ny>m) continue;
            if(wal[{{fr.x,fr.y},{nx,ny}}]) continue;
            if(dor[{{fr.x,fr.y},{nx,ny}}] && ((fr.z>>(dor[{{fr.x,fr.y},{nx,ny}}]-1))&1)==0) continue;
            int now=0;
            if(key[nx][ny]) now=key[nx][ny];
            q.push({nx,ny,fr.d+1,fr.z|now});
        }
    }
    return -1;
}
int main(){
    ios;
    cin>>n>>m>>p>>k;
    while(k--){
        int x1,y1,x2,y2,G;
        cin>>x1>>y1>>x2>>y2>>G;
        if(G==0){
            wal[{{x1,y1},{x2,y2}}]=1;
            wal[{{x2,y2},{x1,y1}}]=1;
        }
        else{
            dor[{{x1,y1},{x2,y2}}]=G;
            dor[{{x2,y2},{x1,y1}}]=G;
        }
    }
    cin>>s;
    for(int i=1;i<=s;i++){
        int x,y,g;
        cin>>x>>y>>g;
        key[x][y]|=(1<<g-1);
    }
    int ans=bfs(1,1);
    cout<<ans<<'\n';
    return 0;
}