题目链接
// luogu-judger-enable-o2
#include <iostream>
#include <queue>
#include <cstring>
#define maxn 1000005
#define inf 0x3f3f
using namespace std;
int row,line,keyn,r;
int M,layer,n;
int num[20][20];
int fg[2001][2001],kn[20];
int tot;
struct typekey
{int x,y;
}key[20][20];
int dis[maxn];
int x,y;
int head[maxn];
struct edge
{int u,v,w;int next;
}e[maxn];
void add(int u,int v,int w)
{e[++tot]=(edge){u,v,w,head[u]};head[u]=tot;
}
bool vis[maxn];
struct node
{int s,val;bool operator < (node a) const{return a.val<val;}
};
priority_queue<node> q;
void init()
{int i,j,k,x,y,p;cin>>row>>line>>keyn>>r;k=0;for(i=1;i<=row;i++)for(j=1;j<=line;j++)num[i][j]=++k;for(i=1;i<=r;i++){cin>>x>>y;j=num[x][y];cin>>x>>y;k=num[x][y];cin>>p;if(p==0) p=-1;fg[j][k]=fg[k][j]=p;}cin>>r;for(i=1;i<=r;i++){cin>>x>>y>>p;kn[p]++;key[p][kn[p]].x=x;key[p][kn[p]].y=y;}
}
void build()
{int k,x,y,t;bool havekey[18]={0};M=row*line;layer=1<<keyn;n=M*layer;for(int k=0;k<layer;k++){for(int i=1;i<=keyn;i++)if(k&(1<<(i-1))) havekey[i]=1;else havekey[i]=0;for(int i=1;i<=row;i++)for(int j=1;j<=line;j++){x=num[i][j];y=num[i][j+1];if(y!=0&&fg[x][y]!=-1){if(fg[x][y]==0||havekey[fg[x][y]]){add(k*M+x,k*M+y,1);add(k*M+y,k*M+x,1);}}y=num[i+1][j];if(y!=0&&fg[x][y]!=-1){if(fg[x][y]==0||havekey[fg[x][y]]){add(k*M+x,k*M+y,1);add(k*M+y,k*M+x,1);}}}for(int i=1;i<=keyn;i++){if(!havekey[i]){t=k+(1<<(i-1));for(int j=1;j<=kn[i];j++){int x=num[key[i][j].x][key[i][j].y];add(k*M+x,t*M+x,0);}}}}
}
void dijkstra()
{memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++) dis[i] = inf;dis[1]=0;q.push((node){1,0});while(!q.empty()){int k = q.top().s;q.pop();if(vis[k]) continue;vis[k] = 1;for(int i = head[k]; i; i = e[i].next) {int v = e[i].v;if(dis[v] > dis[k] + e[i].w) {dis[v] = dis[k] + e[i].w;q.push((node){v,dis[v]});}}}
}
void answer()
{int ans=inf;dijkstra();for(int i=0;i<layer;i++){ans=min(ans,dis[i*(row*line)+num[row][line]]);}if(ans==inf) cout<<"-1"<<endl;else{cout<<ans<<endl;}
}
int main()
{init();build();answer();
}此题为状态压缩的板子题，注意钥匙设计的状态。（感谢lqs大佬的提示）
下位lqs大佬的钥匙设计的例子
#include<bits/stdc++.h>
using namespace std;int main()
{int num = 5; // 有5把钥匙for (int S=0; S<(1<<num); S++) {int a[5];for (int i=0; i<num; i++) {if (S&(1<<i)) a[i]=1;else a[i]=0;}for (int i=0; i<num; i++) printf("%d ", a[i]);printf("\n");}return 0;
}换句话说，状态压缩就是一种分层思想的基础，他通过二进制的方式来枚举状态，从而进行bfs操作或动态规划。