P4011 孤岛营救问题

佚名 6年前 (2019-04-15) 随笔 1941人围观抢沙发百度已收录

d[i][j][k]代表在(i,j)这个坐标点，钥匙集合为二进制k的最短路。

跑一遍Dijkstra即可。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<bits/stdc++.h>
using namespace std;
const int N=15;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
const int INF=0x3f3f3f3f;
int n,m,k,mp[110][110];
vector<int> ys[110];
struct node{
    int x,y,ys;
    int d;
    node() {}
    node(int x,int y,int ys,int d) : x(x),y(y),ys(ys),d(d) {}
    bool operator < (const node &rhs) const {
        return d>rhs.d;
    }
};

int id(int x,int y) { return (x-1)*m+y; }

int d[N][N][1<<12]; bool vis[N][N][1<<12];
priority_queue<node> q;
int Dijkstra() {
    int ret=INF;
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    int tmp=0; for (int i=0;i<ys[1].size();i++) tmp|=ys[1][i];
    d[1][1][tmp]=0; q.push(node(1,1,tmp,0));
    while (!q.empty()) {
        node u=q.top(); q.pop();
        if (u.x==n && u.y==m) ret=min(ret,u.d);
        if (vis[u.x][u.y][u.ys]) continue;
        vis[u.x][u.y][u.ys]=1;
        for (int i=0;i<4;i++) {
            int nx=u.x+dx[i],ny=u.y+dy[i];
            if (nx<1 || nx>n || ny<1 || ny>m || mp[id(u.x,u.y)][id(nx,ny)]==0) continue;
            if (mp[id(u.x,u.y)][id(nx,ny)]>0 && !(u.ys&(1<<mp[id(u.x,u.y)][id(nx,ny)]))) continue;
            int tmp=u.ys;
            for (int j=0;j<ys[id(nx,ny)].size();j++) tmp|=(1<<ys[id(nx,ny)][j]);
            if (d[u.x][u.y][u.ys]+1<d[nx][ny][tmp]) {
                d[nx][ny][tmp]=d[u.x][u.y][u.ys]+1;
                q.push(node(nx,ny,tmp,d[nx][ny][tmp]));
            }
        }
    }
    return ret==INF ? -1 : ret;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    int t; scanf("%d",&t);
    memset(mp,-1,sizeof(mp));
    for (int i=1;i<=t;i++) {
        int x1,y1,x2,y2,p; scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&p);
        mp[id(x1,y1)][id(x2,y2)]=mp[id(x2,y2)][id(x1,y1)]=p;
    }
    scanf("%d",&t);
    for (int i=1;i<=t;i++) {
        int x,y,p; scanf("%d%d%d",&x,&y,&p);
        ys[id(x,y)].push_back(p);
    }
    
    cout<<Dijkstra()<<endl;
    return 0;
}