AcWing 1131. 拯救大兵瑞恩 题解（最短路）

AcWing 1131. 拯救大兵瑞恩
处理数据非常麻烦的一道题，如何建图记录墙和门，利用set记录门，利用二进制记录钥匙进行匹配，这写操作需要学会记住

#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;  //储存邻接表
int dist[N * N][1 << 11];  //储存状态
deque<PII>q;  //储存状态
int n, m, p, k, S;
set<PII>edge;  //记录门 
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(){
      //建图 
	
	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;  //如果出界，就直接跳过
				int a = g[i][j];
				int b = g[xx][yy];
				if(!edge.count({
    a, b})) add(a, b, 0);  //如果这个地方没有门，就是一堵墙 
			}
		}
	}
}

int bfs(){
    
	memset(dist, 0x3f, sizeof dist);
	dist[1][0] = 0;  //状态为第一个点，钥匙为0
	q.push_back({
    1, 0});  //状态为第一个点，钥匙为0 
	
	while(q.size()){
    
		auto op = q.front();
		q.pop_front();
		
		if(st[op.x][op.y]) continue;  //如果这个状态用过
		st[op.x][op.y] = true;
		
		if(op.x == n * m) return dist[op.x][op.y];
		
		if(key[op.x]){
      //如果这个地方有钥匙 
			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(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});  //记录门或墙 
		edge.insert({
    b, a}); 
		if(z){
    
			add(a, b, z);
			add(b, a, z);
		}
	}
	
	build();  //建图 
	
	cin>>S;
	while(S -- ){
    
		int a, b, c;
		cin>>a>>b>>c;
		key[g[a][b]] |= 1 << c - 1;  //用二进制存储钥匙 
 	} 
 	
 	cout<<bfs()<<endl;
 	
 	return 0;
}