标签：str front lap pen continue wal class 技术 void
这题主要问题是有些地方有钥匙，这种类型我们之前在bfs种做到过，就是用状压dp多枚举一维钥匙就行了，因为钥匙不需要时间，所以每次走到取完钥匙肯定是最优的
本题是二维的，不过转成一维更方便。我们的dis数组原先记录的是点，现在记录的是点和状态。建图是，先建门，将门与墙都插入一个set便于查询
建完这两个后，枚举所有位置建立其他没有门墙的地方。
因为本题有两种状态转移的可能，一种是走过一格，一种是在原地获取钥匙，因此边权只有0和1，这种01边权使用双端队列广搜复杂度是线性的
在广搜中，只需要枚举转移即可
#include
#includeset>
#include
#include
#include#define x first
#define y second
using namespace std;
typedef pairint, int> pll;
const int N = 11, M = 360, P = 1 10;
int n, m, k, p;
int h[N * N], e[M], w[M], ne[M], idx;
int g[N][N], key[N*N];
int dis[N * N][P];
bool st[N * N][P];
set node;
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int bfs(){
memset(dis,0x3f,sizeof dis);
dis[1][0]=0;
deque q;
q.push_front({1,0});
while(q.size()){
auto t=q.front();
q.pop_front();
if(t.x==n*m)
return dis[t.x][t.y];
if(st[t.x][t.y])
continue;
st[t.x][t.y]=1;
if(key[t.x]){
int state=t.y|key[t.x];
if(dis[t.x][state]>dis[t.x][t.y]){
dis[t.x][state]=dis[t.x][t.y];
q.push_front({t.x,state});
}
}
int i;
for(i=h[t.x];i!=-1;i=ne[i]){
int j=e[i]; // 没有必要加上位置上的钥匙
//因为这个状态已经被加到队列当种
if(w[i]&&!(t.y>>w[i]-1&1))
continue;//有门但是没钥匙
if(dis[j][t.y]>dis[t.x][t.y]+1){
dis[j][t.y]=dis[t.x][t.y]+1;
q.push_back({j,t.y});
}
}
}
return -1;
}
void build(){
int i,j;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
for(i=1;i){
for(j=1;j){
for(int u=0;u4;u++){
int x=i+dx[u],y=j+dy[u];
if(x>n||x1|y>m||y1)
continue;
int tmp1=g[i][j],tmp2=g[x][y];
if(node.count({tmp1,tmp2}))
continue;
add(tmp1,tmp2,0);
}
}
}
}
int main(){
cin>>n>>m>>p>>k;
int i,j;
int cnt=0;
memset(h,-1,sizeof h);
for(i=1;i){
for(j=1;j){
g[i][j]=++cnt;
}
}
for(i=1;i){
int a,b,c,d,e;
cin>>a>>b>>c>>d>>e;
int tmp1=g[a][b],tmp2=g[c][d];
node.insert(pll{tmp1,tmp2});// the wall or the door
node.insert(pll{tmp2,tmp1});
if(e){
add(tmp1,tmp2,e);
add(tmp2,tmp1,e);
}
}
build();
int s;
cin>>s;
for(i=1;i){
int x,y,c;
cin>>x>>y>>c;
int tmp=g[x][y];
key[tmp]|=11;
}
coutendl;
return 0;
}
View Code
AcWing1131 拯救大兵瑞恩（最短路）
标签：str front lap pen continue wal class 技术 void
原文地址：https://www.cnblogs.com/ctyakwf/p/12823037.html