题解 P3393 【逃离僵尸岛】

· · 题解

这道题模板，其实就两个点，求危险区、把点权转化为边权...然后跑一个最短路即可。 那么我提供一种，比较好理解，但常数比较大的转化方法吧。 通俗来说就是拆点，直观上的边权全部为0，每个点拆为两个，一个只负责进，一个只负责出(就是强行给城市加上出口和入口吧...)，我是把i城市出点的编号改成i+n,他们之间连一条边，边权为房费，于是就完成了...如下图。 拆点思路网络流的题比较常用吧...可能是我最近刷多了，大家了解一下也有好处... 代码如下，这道题并没有卡常...

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#define debug(x) cout<<#x<<":"<<x<<endl
#define ll long long
using namespace std;
const ll maxn=200005;
const ll inf=922337203685477580;
vector<ll> linker[maxn],via[maxn];
ll c[maxn],vis[maxn],d[maxn],m,n,k,s,p,qq,x,y,i,inq[maxn],u,v,w;
inline void addedge(ll x,ll y,ll z){
    linker[x].push_back(y);
    via[x].push_back(z);
}
inline void bfs(){
    queue<ll> q;
    for(ll i=1;i<=n*2;i++)d[i]=0;
    for(ll i=1;i<=k;i++){q.push(c[i]);vis[c[i]]=1;d[c[i]]=0;addedge(c[i],c[i]+n,inf);}
    while(!q.empty()){
        ll e=q.front();q.pop();
        if(d[e]==s)return;
        for(ll i=0;i<linker[e+n].size();i++)
         if(!vis[linker[e+n][i]]){
            d[linker[e+n][i]]=d[e]+1;
            q.push(linker[e+n][i]);
            addedge(linker[e+n][i],linker[e+n][i]+n,qq);
            vis[linker[e+n][i]]=1;
         }
    }
}
void spfa(){       
    queue<ll> q;
    for(i=1;i<=n*2;i++)d[i]=inf;
    d[1+n]=0;inq[1+n]=1;q.push(1+n);
    while(!q.empty()){
        u=q.front();q.pop();inq[u]=0;
        for(i=0;i<linker[u].size();i++){
            v=linker[u][i];w=via[u][i];
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                if(!inq[v]){inq[v]=1;q.push(v);}
            }
        }
    }
    printf("%lld",d[n]);
}
int main(){
    scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&k,&s,&p,&qq);
    for(i=1;i<=k;i++)scanf("%lld",&c[i]);
    for(i=1;i<=m;i++){
        scanf("%lld%lld",&x,&y);
        addedge(x+n,y,0);
        addedge(y+n,x,0);
    }
    bfs();
    for(i=2;i<=n-1;i++)if(!vis[i]){addedge(i,i+n,p);}
    spfa();
    return 0;
}