孤岛营救问题

分层图bfs/spfa
spfa好难写。。。
调不出来，写了bfs
记录持有钥匙的状态，以此分层即可。

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=105,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int n,m,p,k,head[N],ecnt,g[N],key[N],dis[N][1<<14],wal[N][N];
int id(int x,int y) {return (x-1)*m+y;}
struct node {int x,y,k;};
queue<node> q;
void bfs() {
	memset(dis,0x3f,sizeof dis);
	q.push({1,1,0});
	dis[id(1,1)][0]=0;
	while(!q.empty()) {
		node u=q.front();q.pop();
		int x=u.x,y=u.y,k=u.k;
		for(int i=0;i<4;i++) {
			int nx=x+dx[i],ny=y+dy[i];
			int oldd=id(x,y);
			if(nx>0&&nx<=n&&ny>0&&ny<=m) {]
			int now=id(nx,ny);
				if((!wal[now][oldd]||!(wal[now][oldd]&k^wal[now][oldd]))&&dis[now][k|key[now]]>dis[oldd][k]+1) {
					dis[now][k|key[now]]=dis[oldd)][k]+1;
					q.push({nx,ny,k|key[now]});
				}
			}
		}
	}
}
int main() {
	scanf("%d%d%d%d",&n,&m,&p,&k);
	for(int i=1,a,b,c,d; i<=k; i++) {
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&g[i]);
		if(g[i])
			wal[id(a,b)][id(c,d)]=wal[id(c,d)][id(a,b)]=wal[id(a,b)][id(c,d)]|(1<<g[i]-1);
		else wal[id(a,b)][id(c,d)]=wal[id(c,d)][id(a,b)]=wal[id(a,b)][id(c,d)]|(1<<p);
		}
	int keys;
	scanf("%d",&keys);
	for(int x,y,q,i=1; i<=keys; i++) {
		scanf("%d%d%d",&x,&y,&q);
		key[id(x,y)]|=1<<q-1;
	}
	bfs();
	int ans=0x3f3f3f3f;
	for(int i=0; i<(1<<p); i++) {
		ans=min(ans,dis[id(n,m)][i]);
	}
	printf("%d",ans==0x3f3f3f3f?-1:ans);
}