简单的SPFA

孤叶残影 · 2019-10-13 16:52:47 · 题解

（DIJSKRAL应该也能做） 本题利用分层图建立模型，若没有钥匙和门，可直接用最短路算法求解

但有了门的因素，可建立2的p次方层（共有p种钥匙，每种钥匙有有与没有两种状态，共计2的p次方）。

对于分层图连边

再同一层中，在相邻两点间连一条权值为1的边（双向），若该点有一把k种钥匙，则在该点与有第k种钥匙状态的那一层连一条权值为0的边，然后BFS

#include<bits/stdc++.h>
using namespace std;
struct node{
    int to,next,w;
}a[1000000];
struct typekey{
    int x,y;
}key[15][20];
int n,M,tot=0,row,line,keyn;
int layer,r,num[20][20];
int fg[200][200],kn[15],frist[102405],dis[102405];
int q[1000000],inf=1e9;
bool vst[102405];
inline void scan()
{
    int i,j,x,y,p,k=0;
    scanf("%d %d %d %d",&row,&line,&keyn,&r);
    for(i=1;i<=row;i++)
    {
        for(j=1;j<=line;j++)
        num[i][j]=++k;         //编号
    }
    for(i=1;i<=r;i++)
    {
        scanf("%d %d",&x,&y);
        j=num[x][y];
        scanf("%d %d",&x,&y);
        k=num[x][y];
        scanf("%d",&p);
        if(p==0) p=-1;            //表示围墙
        fg[j][k]=fg[k][j]=p;
    }
    scanf("%d",&r);
    for(i=1;i<=r;i++)
    {
        scanf("%d %d %d",&x,&y,&p);
        kn[p]++;
        key[p][kn[p]].x=x;      //key[p][kn[p]]为第p类钥匙的第kn[p]把所在的位置
        key[p][kn[p]].y=y;
    }
}
inline void add_edge( int x,int y,int w)
{
    tot++;
    a[tot].to=y;
    a[tot].w=w;
    a[tot].next=frist[x];
    frist[x]=tot;

}
inline void process()
{
    int i,j,k,x,y,t;
    bool havekey[15]={0};
    M=row*line;         //每层节点数
    layer=1<<keyn;     //共有layer层数 
    n=M*layer;           //总节点数
    for(k=0;k<layer;k++)         //对每层处理
    {
        for(i=1;i<=keyn;i++)
        if(k&(1<<(i-1))) havekey[i]=true;
        else havekey[i]=false;
        for(i=1;i<=row;i++)         //在本层连边
        {
            for(j=1;j<=line;j++)
            {
                x=num[i][j];
                y=num[i][j+1];       //向右连接
                if(y!=0&&fg[x][y]!=-1)   //有节点且两点间无墙
                {
                    if(fg[x][y]==0||havekey[fg[x][y]])
                    {
                        add_edge(k*M+x,k*M+y,1);
                        add_edge(k*M+y,k*M+x,1);
                    }
                }
                y=num[i+1][j];            //向下连边
                if(y!=0&&fg[x][y]!=-1)
                {
                    if(fg[x][y]==0||havekey[fg[x][y]])
                    {
                        add_edge(k*M+x,k*M+y,1);
                        add_edge(k*M+y,k*M+x,1);
                    }
                }           
            }
        }
        for(i=1;i<=keyn;i++)           //转移到其他状态
        {
            if(!havekey[i])            //未持有i类钥匙转移
            {
                t=k+(1<<(i-1));       //得到i类钥匙的层
                for(j=1;j<=kn[i];j++)     //循环i类钥匙位置
                {
                    x=num[key[i][j].x][key[i][j].y];
                    add_edge(k*M+x,t*M+x,0);
                }
            }
        }
    } 
}
inline void SPFA()
{
    int i,j,k,head,tail;
    for(i=1;i<=n;i++) dis[i]=inf;
    dis[1]=0;vst[1]=true;head=tail=1;q[1]=1;
    while(head<=tail)
    {
        i=q[head];
        for(k=frist[i];k;k=a[k].next)
        {
            j=a[k].to;
            if(dis[j]>dis[i]+a[k].w)
            {
                dis[j]=dis[i]+a[k].w;
                if(!vst[j])
                {
                    q[++tail]=j;
                    vst[j]=true;
                }
            }
        }
        vst[i]=false;
        head++;
    }
}
inline void end()
{
    int i,ans=inf,T;
    SPFA();
    T=num[row][line];
    for(i=0;i<layer;i++)
    ans=min(ans,dis[i*M+T]);
    if(ans<inf) printf("%d",ans);
    else printf("-1");
}
int main()
{
    scan();
    process();//建图
    end();
    return 0;
}