题目链接
洛谷链接：https://www.luogu.com.cn/problem/P4011
AcWing链接：https://www.acwing.com/problem/content/1133/
涉及知识
1.单源最短路
2.双端队列广度优先搜索
3.状态压缩动态规划和二进制的巧用
思路分析
第一部分：题意的抽象——建图
首先我们看到这一题，不难想到这是一个限制条件较多的最短路，那么我们就很自然地需要探索如何将本题的门、墙、钥匙等抽象成图、边等元素。
图的基本元素是点和边，因此，我们也就围绕着两个元素展开。
点
点，即当前麦克所在的地方。本题是以坐标的形式给到我们的，这方便我们进行DFS或者BFS的转移，但是不方便我们运用最短路算法的，我们可以通过初始化赋值，将每一个二维坐标转化为一维坐标，并且在题中灵活运用这两种坐标。（这一点会在之后的代码中有所体现）
同时，每个点可能会有钥匙，也就是说，与经典最短路相比，我们还需要考虑走到当前点时我们手中拿到的钥匙的情况。对于这一点，我们可以借鉴状态压缩动态规划的思想，将当前拿到的钥匙的情况用二进制数表示。特别注意，本题中同一处地方可能会有多把钥匙，因此我们在读入钥匙的坐标时，不能简单地用等于，而是用或操作合并。在宽搜走到要通过大门时，则读取状态判断有无该类型的钥匙。
在这里对于所涉及的二进制操作在状态压缩中的利用进行简单介绍，至于每一种运算符的含义，如果没有接触过请自行查阅资料，有学过状压的可以略过：
1.简介：在信息学的题目中，我们常用二进制数来表示某一种状态，比如动态规划中当前我们持有的物品。以本题为例，我们想用二进制数表示当前我们持有x xx类型的钥匙，本质上就是让二进制数的第x xx位变成 1 。在之后的读取中，哪一位有 1，就说明我们有哪一种钥匙。这也就解释了，为什么开数组时的P PP要设置为1 < < 10 1<<101<<10(即等同于2 10 2^{10}210)，因为共有 10 钟类型的钥匙，每一种类型的钥匙我么可能持有（状态为1），可能没有（状态为0），两种情况。
2.合并状态：在二进制操作中，我们采用或操作来合并两种状态。这里可以类比数学中的集合，一个集合，我们做并集运算，其实就是把两个集合都有的元素通通放进来。或操作对两个二进制数的每一位进行判断，只要其中有 1 位为 1，结果便为 1，也就是说只要我两种状态中有任意一种状态拥有这种类型的钥匙，最后结果都会拥有。通过或操作，我们就保证了当一个地方有多种类型的钥匙时，结果都在取并集。
3.读入状态：以此题为例，当我们拥有x xx类型的钥匙时，读入便是让二进制数的第x xx位为 1。通过左移x xx位，让第x xx位变成1，得到一个新二进制数000..1...00 000..1...00000..1...00（1在第x xx位），再用当前状态的二进制数和它做或运算即可得到新状态。
4.读取状态：读取状态便是希望取出第x xx位的数字，判断其是否为1 11，从而得出是否拥有x xx类型的钥匙。设当前状态为s ss，则通过右移操作s > > x s>>xs>>x是在取出第x xx位，s > > x & 1 s>>x\&1s>>x&1就是在判断第x xx位是否为 1。
边
边，即题中的门、墙和其他自由通行的路径。
1.门和墙：门，我们可以直接读入，将边权设定为其所属的类型即可。需要注意的是，墙我们是不需要读入的，因为我们是在做图论题，只要不建边就不会有这条路，也就不会通行了。
2.自由通行的路径：自由通行的路径相当于一扇不需要任何钥匙的“门”，所以可以在读入完门和墙的数据之后，用一个函数把自由通行的路径一次性初始化好，设定为边权为 0 的边。为了防止给一扇门或者一堵墙所在的那条边也建上自由通行的路径，我们可以在读入门和墙的时候用s e t setset统计已经出现的边。
第二部分：最短路的实现
在本题中，我们可以将捡到钥匙看作边权为 0 的边，将朝四周走看作边权为 1 的边，也就是两种可能的情况，然后运用双端队列BFS，即可得出走到瑞恩处的最短距离。
需要注意的是，此处的边权并非上面我们建边时的边权，建边时我们只是用存储边权的数组存储了钥匙的类型；而我们真正意义上的边权，即我们跑最短路时走一步加的那个数字，只是1。
第三部分：思路再梳理
第一步：读入n , m , p , k n,m,p,kn,m,p,k以及门和墙的数据，统计所有已经出现的门和墙，类型为门的边进行建边，然后将其他可以自由通行的路径统一建边；
第二步：读入所有钥匙的所在处，通过状态压缩记录每个点的钥匙情况；
第三步：双端队列 BFS跑最短路，分为此点有无钥匙和走下一步两个部分分别求解最短路，记录以某种状态到达某点时的最短路
AC代码
#include<iostream>#include<cstdio>#include<algorithm>#include<deque>#include<cstring>#include<set>usingnamespacestd;constintN=11,M=N*N,E=400,P=1<<10,INF=0x3f3f3f3f;typedefpair<int,int>PII;intn,m,p,k;intst[M][P],dis[M][P];intne[E],h[M],e[E],w[E],idx;intG[N][N],key[M];set<PII>edges;voidadd(inta,intb,intc){w[idx]=c;e[idx]=b;ne[idx]=h[a];h[a]=idx++;return;}voidbuild(){intdx[]={-1,0,1,0},dy[]={0,1,0,-1};for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){for(intu=0;u<4;u++){intvx=i+dx[u],vy=j+dy[u];if(vx<0||vx>n||vy<0||vy>m)continue;inta=G[i][j],b=G[vx][vy];if(edges.count({a,b})==0)add(a,b,0);}}}return;}intbfs(){//哪个点，什么状态memset(dis,INF,sizeofdis);dis[1][0]=0;deque<PII>q;q.push_back({1,0});while(!q.empty()){autonow=q.front();q.pop_front();intnowu=now.first,now_state=now.second;if(st[nowu][now_state])continue;st[nowu][now_state]=true;//到了就可以直接输出if(nowu==n*m)returndis[nowu][now_state];//先判断这里有钥匙没if(key[nowu]){intne_state=now_state|key[nowu];if(dis[nowu][ne_state]>dis[nowu][now_state]){dis[nowu][ne_state]=dis[nowu][now_state];q.push_front({nowu,ne_state});}}//继续走for(inti=h[nowu];i!=-1;i=ne[i]){intj=e[i];//有门且没有钥匙if(w[i]&&!(now_state>>w[i]&1))continue;if(dis[j][now_state]>dis[nowu][now_state]+1){dis[j][now_state]=dis[nowu][now_state]+1;q.push_back({j,now_state});}}}return-1;}intmain(){memset(h,-1,sizeofh);scanf("%d%d%d%d",&n,&m,&p,&k);//给每个点赋值for(inti=1,t=1;i<=n;i++){for(intj=1;j<=m;j++){G[i][j]=t++;}}for(inti=1;i<=k;i++){intx1,y1,x2,y2,type;scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&type);inta=G[x1][y1],b=G[x2][y2];edges.insert({a,b});edges.insert({b,a});if(type){add(a,b,type);add(b,a,type);}}build();//建立其他边ints;scanf("%d",&s);for(inti=1;i<=s;i++){intx,y,id;scanf("%d%d%d",&x,&y,&id);key[G[x][y]]|=1<<id;}intans=bfs();printf("%d",ans);return0;}
