洛谷P3393题解：基于多源BFS与Dijkstra算法求解图论最小花费路径问题
一、题目解读
洛谷P3393题要求在一个包含N个城市和M条双向道路的图中，求解从起点1到终点N的最小花费路径。图中存在僵尸城市（僵尸无法通过）和危险城市（由僵尸城市扩散S步后标记），需要避开所有危险城市，同时每个城市有住宿费用。题目保证有解，需利用图论算法优化路径计算。
二、解题思路
1. 多源BFS标记危险城市：由于僵尸城市会向四周扩散S步形成危险区域，采用多源BFS遍历所有僵尸城市，标记其S步内可达的城市为危险（isDanger数组）。
2. Dijkstra算法求最短路：在避开危险城市的前提下，利用Dijkstra从起点开始计算到终点N的最小总花费（住宿费用累加）。
3. 优化点：通过优先队列维护当前最短路径，跳过僵尸城市以减少无效搜索，确保算法效率。
三、解题步骤
1. 数据初始化：读取城市数量N、道路数M、僵尸城市数K和扩散步数S，构建邻接表graph存储图结构，初始化危险、僵尸标记及费用数组。
2. 标记危险城市：调用markDangerCities函数，对所有僵尸城市进行BFS，使用队列记录当前城市和步数，当步数超过S时停止扩散。
3. 执行Dijkstra算法：
初始化起点1的最小花费为0，其余城市为无穷大。
用优先队列维护当前待扩展节点（距离，城市编号）。
循环直至终点N被访问或队列为空，每次取出当前距离最小的节点u，遍历其邻居v：
若v为僵尸城市或危险城市，跳过。
计算新路径花费（当前距离+城市v的住宿费用），若更优则更新dist[v]并加入队列。
4. 输出结果：返回终点N的最小花费，若无法到达则为-1（但题目保证有解）。
四、代码与注释
#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}); // 入队，步数初始化为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; // 起点距离为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;
}
五、总结
本文通过结合多源BFS与Dijkstra算法，高效解决了洛谷P3393题中的图论路径问题。关键在于预处理危险城市范围，避免无效搜索，同时利用优先队列优化路径选择。代码简洁且符合题目要求，为类似图论问题提供了可行的解题思路。需注意题目数据范围和算法时间复杂度分析（O(N+MlogN)），确保在实际应用中的可行性。
原创内容 转载请注明出处
