P3393 逃离僵尸岛

P3393 逃离僵尸岛 - 洛谷 

多源BFS ---------->把所有直接占领点压入队列，bfs求解距离

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define int long long 

const int N=5e5+5;

std::vector<int>edge[N];
int n,m,k,s,cost1,cost2;
int occupy[N],val[N],dist[N],vis[N],cant[N];

void bfs(){
    queue<pair<int,int>>q;
    for(int i=1;i<=n;i++)q.push({occupy[i],0});
    while(!q.empty()){
        auto [x,dis]=q.front();
        q.pop();
        if(dis>s)continue;
        if(vis[x])continue;
        vis[x]=1;
        val[x]=cost2;
        for(auto y:edge[x]){
            if(!vis[y])q.push({y,dis+1});
        }
    }    
}

void Dijkstra(int s){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    for(int i=1;i<=n;i++)dist[i]=21474836476666;
    q.push({0,1});
    dist[1]=0;
    while(!q.empty()){
        auto [v,x]=q.top();
        q.pop();
        for(auto y:edge[x]){
            if(!cant[y]&&v+val[y]<dist[y]){
                dist[y]=v+val[y];
                q.push({dist[y],y});
            }
        }
    }
}


signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k>>s;
    cin>>cost1>>cost2;
    for(int i=1;i<=k;i++){
        cin>>occupy[i];
        cant[occupy[i]]=1;
    }
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    bfs();
    for(int i=2;i<=n;i++){
        if(!vis[i])val[i]=cost1;
    }
    Dijkstra(1);
    if(val[n]==cost1)cout<<dist[n]-cost1<<endl;
    else cout<<dist[n]-cost2<<endl;
    return 0;
}