AcWing 1131. Saving Private Ryan (the shortest way)

AcWing 1131. Saving Private Ryan
Dealing with data is a very troublesome problem , How to build drawings to record walls and doors , utilize set Record gate , Match with binary record key , This writing operation needs to be learned to remember

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef pair<int, int>PII;

const int N = 15, M = 360, INF = 0x3f3f3f3f;

int h[N * N], ne[M], e[M], w[M], idx;  // Store adjacency table 
int dist[N * N][1 << 11];  // Storage status 
deque<PII>q;  // Storage status 
int n, m, p, k, S;
set<PII>edge;  // Record gate  
int g[N][N];
int dx[4] = {
    1, 0, -1, 0};
int dy[4] = {
    0, 1, 0, -1};
int key[N * N];
bool st[N * N][1 << 11];

void add(int a, int b, int c){
    
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx ++ ;
} 

void build(){
      // Drawing  
	
	for(int i = 1; i <= n; i ++ ){
    
		for(int j = 1; j <= m; j ++ ){
    
			for(int k = 0; k < 4; k ++ ){
    
				int xx = dx[k] + i;
				int yy = dy[k] + j;
				if(!xx || !yy || xx > n || yy > m) continue;  // If out of bounds , Just skip it 
				int a = g[i][j];
				int b = g[xx][yy];
				if(!edge.count({
    a, b})) add(a, b, 0);  // If there is no door in this place , It's just a wall  
			}
		}
	}
}

int bfs(){
    
	memset(dist, 0x3f, sizeof dist);
	dist[1][0] = 0;  // The status is the first point , The key is 0
	q.push_back({
    1, 0});  // The status is the first point , The key is 0 
	
	while(q.size()){
    
		auto op = q.front();
		q.pop_front();
		
		if(st[op.x][op.y]) continue;  // If this state has been used 
		st[op.x][op.y] = true;
		
		if(op.x == n * m) return dist[op.x][op.y];
		
		if(key[op.x]){
      // If there is a key in this place  
			int state = op.y | key[op.x];
			if(dist[op.x][state] > dist[op.x][op.y]){
    
				dist[op.x][state] = dist[op.x][op.y];
				q.push_front({
    op.x, state});
			}
		} 
		
		for(int i = h[op.x]; ~i; i = ne[i]){
    
			int j = e[i];
			if(w[i] && !(op.y >> w[i] - 1 & 1)) continue;  // If there is a door here but there is no key  
			if(dist[j][op.y] > dist[op.x][op.y] + 1){
      //
				dist[j][op.y] = dist[op.x][op.y] + 1;
				q.push_back({
    j, op.y});
			}
		}
	}
	return -1;
}

int main()
{
    
	cin>>n>>m>>p>>k;
	
	for(int t = 1, i = 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, z;
		cin>>x1>>y1>>x2>>y2>>z;
		int a = g[x1][y1], b = g[x2][y2];
		edge.insert({
    a, b});  // Record door or wall  
		edge.insert({
    b, a}); 
		if(z){
    
			add(a, b, z);
			add(b, a, z);
		}
	}
	
	build();  // Drawing  
	
	cin>>S;
	while(S -- ){
    
		int a, b, c;
		cin>>a>>b>>c;
		key[g[a][b]] |= 1 << c - 1;  // Store keys in binary  
 	} 
 	
 	cout<<bfs()<<endl;
 	
 	return 0;
}