洛谷P3393题 逃离僵尸岛：用BFS和Dijkstra算法规划最优逃生路线

一、问题分析

题目描述了一个国家被僵尸侵略的场景，我们需要帮助主角小a找到从1号城市到N号城市的最小花费路径。关键点包括：

1. ‌危险城市判定‌：距离任何僵尸城市不超过S条道路的城市都是危险的

2. ‌住宿费用差异‌：安全城市住宿费P元，危险城市Q元（Q > P）

3. ‌路径限制‌：不能进入任何僵尸城市

二、解题思路

1. ‌多源BFS‌：从所有僵尸城市出发，计算每个城市到最近僵尸城市的距离

2. ‌危险城市标记‌：距离≤S的城市标记为危险城市

3. ‌费用预处理‌：根据城市类型设置住宿费用

4. ‌Dijkstra算法‌：计算考虑住宿费用的最短路径

三、关键算法详解

1. 多源BFS

void markDangerCities(int N, int S) {
    queue<pair<int, int>> q;    vector<int> dangerDist(N + 1, -1);    
    // 初始化队列
    for (int i = 1; i <= N; ++i) {        if (isZombie[i]) {
            q.push({i, 0});
            dangerDist[i] = 0;
        }
    }    
    // BFS扩展
    while (!q.empty()) {        auto [u, d] = q.front();
        q.pop();        
        if (d >= S) continue;        
        for (int v : graph[u]) {            if (dangerDist[v] == -1) {
                dangerDist[v] = d + 1;
                q.push({v, d + 1});
                isDanger[v] = true;
            }
        }
    }
}

这个BFS从所有僵尸城市同时出发，记录每个城市到最近僵尸城市的距离。时间复杂度O(N+M)。

2. Dijkstra算法

ll dijkstra(int N) {
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;    fill(dist, dist + N + 1, LLONG_MAX);
    
    dist[1] = 0;
    pq.push({0, 1});    
    while (!pq.empty()) {        auto [currentDist, u] = pq.top();
        pq.pop();        
        if (u == N) return currentDist;        if (currentDist > dist[u]) continue;        
        for (int v : graph[u]) {            if (isZombie[v]) continue;
            
            ll newDist = currentDist + cost[v];            if (newDist < dist[v]) {
                dist[v] = newDist;
                pq.push({newDist, v});
            }
        }
    }    return -1;
}

使用优先队列优化的Dijkstra算法，时间复杂度O(M log N)。注意跳过僵尸城市，并考虑住宿费用。

四、完整代码

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef long long ll;
const int MAXN = 1e5 + 5;

vector<int> graph[MAXN];  // 邻接表存储图
bool isDanger[MAXN];      // 标记危险城市
bool isZombie[MAXN];      // 标记僵尸城市
ll cost[MAXN];            // 每个城市的住宿费用
ll dist[MAXN];            // 到每个城市的最小花费

// 多源BFS计算危险城市
void markDangerCities(int N, int S) {
    queue<pair<int, int>> q;
    vector<int> dangerDist(N + 1, -1);
    
    // 初始化僵尸城市
    for (int i = 1; i <= N; ++i) {
        if (isZombie[i]) {
            q.push({i, 0});
            dangerDist[i] = 0;
        }
    }
    
    // BFS扩展
    while (!q.empty()) {
        auto [u, d] = q.front();
        q.pop();
        
        if (d >= S) continue;
        
        for (int v : graph[u]) {
            if (dangerDist[v] == -1) {
                dangerDist[v] = d + 1;
                q.push({v, d + 1});
                isDanger[v] = true;
            }
        }
    }
}

// Dijkstra算法求最短路
ll dijkstra(int N) {
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    fill(dist, dist + N + 1, LLONG_MAX);
    
    dist[1] = 0;
    pq.push({0, 1});
    
    while (!pq.empty()) {
        auto [currentDist, u] = pq.top();
        pq.pop();
        
        if (u == N) return currentDist;
        if (currentDist > dist[u]) continue;
        
        for (int v : graph[u]) {
            if (isZombie[v]) continue;  // 跳过僵尸城市
            
            ll newDist = currentDist + cost[v];
            if (newDist < dist[v]) {
                dist[v] = newDist;
                pq.push({newDist, v});
            }
        }
    }
    return -1;  // 题目保证有解，这里不会执行
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M, K, S;
    cin >> N >> M >> K >> S;
    
    int P, Q;
    cin >> P >> Q;
    
    // 读取僵尸城市
    for (int i = 0; i < K; ++i) {
        int c;
        cin >> c;
        isZombie[c] = true;
    }
    
    // 读取道路
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    // 标记危险城市
    markDangerCities(N, S);
    
    // 设置每个城市的住宿费用
    for (int i = 1; i <= N; ++i) {
        if (i == 1 || i == N) {
            cost[i] = 0;  // 起点和终点不需要住宿
        } else if (isZombie[i]) {
            cost[i] = LLONG_MAX;  // 不能进入僵尸城市
        } else if (isDanger[i]) {
            cost[i] = Q;
        } else {
            cost[i] = P;
        }
    }
    
    cout << dijkstra(N) << endl;
    
    return 0;
}