Luogu-P3393-逃离僵尸岛

题目 P3393 逃离僵尸岛

题目描述

小 a 住的国家被僵尸侵略了！小 a 打算逃离到该国唯一的国际空港逃出这个国家。

该国有 $N$ 个城市，城市之间有道路相连。一共有 $M$ 条双向道路。保证没有自环和重边。

其中 $K$ 个城市已经被僵尸控制了，如果贸然闯入就会被感染 TAT…所以不能进入。由其中任意城市经过不超过 $S$ 条道路就可以到达的别的城市，就是危险城市。换句话说只要某个城市到任意被僵尸控制的城市距离不超过 $S$，就是危险的。

小 a 住在 $1$ 号城市，国际空港在 $N$ 号城市，这两座城市没有被侵略。小a走每一段道路（从一个城市直接到达另外一个城市）得花一整个白天，所以晚上要住旅店。安全的的城市旅馆比较便宜要 $P$ 元，而被危险的城市，旅馆要进行安保措施，所以会变贵，为 $Q$ 元。所有危险的城市的住宿价格一样，安全的城市也是。在 $1$ 号城市和 $N$ 城市，不需要住店。

小 a 比较抠门，所以他希望知道从 $1$ 号城市到 $N$ 号城市所需要的最小花费。

输入数据保证存在路径，可以成功逃离。输入数据保证他可以逃离成功。

输入格式

第一行 4 个整数 $N,M,K,S$。

第二行两个整数 $P,Q$。

接下来 $K$ 行，每行一个整数 $c_i$，表示僵尸侵占的城市编号。

接下来 $M$ 行，$a_i,b_i$，表示一条无向边。

输出格式

一个整数表示最低花费。

思路：bfs，最短路

使用邻接表建图，此处略。

注意无向图的二倍空间。

僵尸的处理

首先使用 $zombie[i]$ 数组记录第 $i$ 个点是否被僵尸占领。

对于被僵尸占领的点，不能经过它，并且对它 $S$ 格以内的点标记上危险，使用 $exps[x]$ 表示第 $x$ 个点是否危险（价格贵）。

此处使用广度优先，使用深度优先可能会出错或时间复杂度较高。

void mark(int x) {
    auto q = queue<pair<int, int>>();
    q.push({x, 0});
    vis[x] = true;
    while(q.size()) {
        auto n = q.front();
        q.pop();
        exps[n.first] = true;
        if(n.second < S) {
            for(int i = head[n.first]; i; i = edge[i].next) {
                int to = edge[i].to;
                if(vis[to]) continue;
                vis[to] = true;
                q.push({to, n.second + 1});
            }
        }
    }
}

点权转换

可以考虑，$1$ 号点到 $i$ 号点的消费为“路径长度”。

这样就转化为了最短路问题。

最短路

有僵尸的点跳过。

考虑使用 $money$ 数组（长度为 $2$）记录普通和危险节点的价格。

这样，第 $i$ 个点的价格为：$money[exps[i]]$，从而简化思路。

注意会爆int！

ll min_cost() {
    set(dis, inf);
    dis[1] = 0;
    priority_queue<node> q;
    q.push({1});
    while(q.size()) {
        int from = q.top().from;
        vis[from] = true;
        q.pop();
        for(int i = head[from]; i; i = edge[i].next) {
            int to = edge[i].to;
            if(vis[to]) continue;
            if(zombie[to]) continue;
            if(dis[from] + money[exps[to]] < dis[to]) {
                dis[to] = dis[from] + money[exps[to]];
                vis[to] = true;
                q.push({to});
            }
        }
    }
    return dis[n] - money[exps[n]];
}

AC Code

// template v9
#include <bits/stdc++.h>
#define set(x, y) memset(x, y, sizeof x)

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

const int N = 1e5 + 10;
const int M = 2e5 + 10;
int n, m, K, S;
ll money[2];

bool exps[N];
bool zombie[N];

int head[N];
ll dis[N];
int pt = 1;

struct Edge {
    int to, next;
} edge[2 * M];

struct node {
    int from;
    bool operator<(const node &e) const {
        return dis[from] > dis[e.from];
    }
};

void add_edge(int from, int to) {
    Edge &e = edge[pt];
    e.to = to;
    e.next = head[from];
    head[from] = pt;
    pt++;
}

bool vis[N];

ll min_cost() {
    set(dis, inf);
    dis[1] = 0;
    priority_queue<node> q;
    q.push({1});
    while(q.size()) {
        int from = q.top().from;
        vis[from] = true;
        q.pop();
        for(int i = head[from]; i; i = edge[i].next) {
            int to = edge[i].to;
            if(vis[to]) continue;
            if(zombie[to]) continue;
            if(dis[from] + money[exps[to]] < dis[to]) {
                dis[to] = dis[from] + money[exps[to]];
                vis[to] = true;
                q.push({to});
            }
        }
    }
    return dis[n] - money[exps[n]];
}

void mark(int x) {
    auto q = queue<pair<int, int>>();
    q.push({x, 0});
    vis[x] = true;
    while(q.size()) {
        auto n = q.front();
        q.pop();
        exps[n.first] = true;
        if(n.second < S) {
            for(int i = head[n.first]; i; i = edge[i].next) {
                int to = edge[i].to;
                if(vis[to]) continue;
                vis[to] = true;
                q.push({to, n.second + 1});
            }
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("diyi.in", "r", stdin);
    freopen("diyi.out", "w", stdout);
#endif
    cin >> n >> m >> K >> S;
    cin >> money[0] >> money[1];
    int t1, t2;
    for(int i = 0; i < K; i++) {
        cin >> t1;
        zombie[t1] = true;
    }
    for(int i = 0; i < m; i++) {
        cin >> t1 >> t2;
        add_edge(t1, t2);
        add_edge(t2, t1);
    }
    for(int i = 1; i <= n; i++) {
        if(zombie[i]) {
            mark(i);
            set(vis, 0);
        }
    }
    cout << min_cost() << endl;
    return 0;
}