【luogu4011】孤岛营救问题(拯救大兵瑞恩) [最短路][分层思想]

P4011 孤岛营救问题

 

我可能是个废人 按着书上打都能搞一上午

好像是个网络流的题 还在网络流24题里 结果没一个写网络流 要不是bfs要不就是最短路

想练dijkstra 结果例二就给我来个这个东西 把书上程序spfa改成dijkstra

开始忘了运行build函数然后死活输出-1QAQ 后面又数组开小了 全！都！开！小！了！开！小！了！小！了！

一直都没想过数组小了会和输出答案有关 一直看看看看 看书看程序 然后突然开窍 我是不是数组开小了？然后.......

把每个(X,Y)的单元看作一个点 然后相互联通的单元连一条权值为1的边

然后就是连边了 把图分为2^p层 就是状态压缩 每层分别为拥有钥匙的状态 然后根据状态来连边建图。 对于有钥匙的点 就将它向对应有钥匙的点连一条权值为0的边

过程比较玄幻

/*
id:gww
language:C--
Kruskal模版！ 
*/
#include<bits/stdc++.h>
using namespace std;
#define rg register
const int N=20,inf=0x3f3f3f3f;
int row,line,nk,zk,nw,num[N][N],tot=0;
//列 行 钥匙数 门/墙 标号 
int mp[N*N][N*N],kn[N];
struct key
{
    int x,y;
}ky[N][N*N];
inline int rd()
{
    int x=0,w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return w?-x:x;
}

int head[1000000],cnt=0;
struct edge
{
    int v,nxt,w;
}e[1000000];
void add(int u,int v,int w)
{
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

bool havek[N];
int m,n,layer;
void build()
{
    layer=1<<zk,n=tot*layer;
    //每层节点数 层数 总结点数
    for(int s=0;s<layer;s++)
    {
        for(int i=1;i<=zk;i++)//当前状态是否有钥匙 
        if(s&(1<<(i-1))) havek[i]=1;
        else havek[i]=0;
        for(int i=1;i<=row;i++)
        for(int j=1;j<=line;j++)
        {
            int pos1=num[i][j],pos2=num[i][j+1];//向右
            if(pos2&&mp[pos1][pos2]+1)//有节点且非墙
            if(!mp[pos1][pos2]||havek[mp[pos1][pos2]])//无门||有钥匙
            add(pos1+tot*s,pos2+tot*s,1),add(pos2+tot*s,pos1+tot*s,1);
            pos2=num[i+1][j];//向下 
            if(pos2&&mp[pos1][pos2]+1)//有节点且非墙
            if(!mp[pos1][pos2]||havek[mp[pos1][pos2]])//无门||有钥匙
            add(pos1+tot*s,pos2+tot*s,1),add(pos2+tot*s,pos1+tot*s,1);
        }
        for(int i=1;i<=zk;i++)//转移到其他状态
        if(!havek[i])//么得钥匙才转移
        {
            int is=(s+(1<<(i-1)));//目标状态
            for(int j=1;j<=kn[i];j++)
            {
                int pos=num[ky[i][j].x][ky[i][j].y];
                add(pos+tot*s,pos+tot*is,0);
            }
        }
     } 
}
struct node
{
    int dis,pos;
    node():dis(0),pos(0){}
    node(int a,int b):dis(a),pos(b){}
    bool operator <(const node &x)const
    {return x.dis<dis;}
};
int dis[N<<N];bool vis[N<<N];
priority_queue<node> q;
void dij(int x)
{
    for(int i=1;i<=n;i++) dis[i]=inf,vis[i]=0;
    dis[x]=0;q.push(node(0,x));
    while(q.size())
    {
        int u=q.top().pos;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v,w=e[i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                q.push(node(dis[v],v));
            }
        }
    }
}

int main()
{
    row=rd(),line=rd(),zk=rd(),nw=rd();
    for(rg int i=1;i<=row;i++)//初始化标号 
    for(rg int j=1;j<=line;j++) num[i][j]=++tot;
    for(int i=1;i<=nw;i++)
    {
        int x1=rd(),y1=rd(),x2=rd(),y2=rd(),g=rd();
        int pos1=num[x1][y1],pos2=num[x2][y2];
        if(g==0) g=-1;//为墙 
        mp[pos1][pos2]=mp[pos2][pos1]=g;
    }
    nk=rd();
    for(int i=1;i<=nk;i++)
    {
        int x=rd(),y=rd(),g=rd();
        ky[g][++kn[g]].x=x,ky[g][kn[g]].y=y;
    }
    build();
    dij(1);
    int ans=inf;
    for(int i=0;i<layer;i++)
    ans=min(ans,dis[i*tot+tot]);
    if(ans<inf) printf("%d",ans);
    else printf("-1");
    return 0;
}