当前位置：首页 > backend >正文

ch11 课堂参考代码及题目参考思路

backend 2025/8/12 10:36:19

ch11 最短路Ⅰ

Dijkstra 算法

Dijkstra 算法基于贪心思想，它只适用于所有边权都是非负数的图。

Dijkstra 算法的正确性可类比 BFS 搜索，都一样是由近到远的顺序，因此能保证每次取出来的 d[u] 最小的 u 就是确定了最短路的。

$O(n^2)$

参考代码：

using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 5010;
ll w[maxn][maxn];
// 是否已确定最短路
bool vis[maxn];
// 只经过已确定最短路的点到点 i 的最短路
ll d[maxn];
int n;/*
标记起点 d[s] = 0 
循环地执行：查找还未确定最短路，且当前 d 最小的点 u点 u 的最短路即为 d[u]确定点 u 的最短路：更新 vis[u], 更新与 u 相连的点的 d[v]
直到 n 个点全部确定最短路
*/
// dij: 单源最短路; s: 源点
void dij(int s) {memset(d, 0x3f, sizeof(d));d[s] = 0;for (int i = 1; i <= n; ++i) {int u = -1;for (int v = 1; v <= n; ++v) {if (!vis[v] && (u == -1 || d[v] < d[u])) u = v;}if (d[u] == inf) return; // 剩余点都与 s 不连通，结束程序vis[u] = 1;for (int v = 1; v <= n; ++v) {if (!vis[v]) d[v] = min(d[v], d[u] + w[u][v]);}}
} 
int main(){memset(w, 0x3f, sizeof(w));int m, s = 1, u, v, _w;cin >> n >> m;for (int i = 1; i <= n; ++i) w[i][i] = 0;for (int i = 0; i < m; ++i) {cin >> u >> v >> _w;w[u][v] = min(w[u][v], (ll)_w);}dij(s);for (int i = 1; i <= n; ++i) cout << d[i] << " ";return 0;
}

以上代码有 2 层循环，时间复杂度 $O(n^2)$ 。

优化 $O(m\log m)$

扫描 u 的所有出边，改为邻接表（vector 写法）储存图，就不用像邻接矩阵一样枚举 1 到 n 每个结点。

主要瓶颈在于第 2 步寻找 u 的过程，要找 d[u] 最小的 u，使用优先队列，令队头就是 d[u] 最小的，不用一个个结点枚举查找。

不能只往优先队列中储存 d[u] 的值，还需要把结点编号 u 也附带在一起。可用 pair 类型（或 struct 类型）来表示，first 储存 d[u]，second 储存 u。

参考代码：

#include <bits/stdc++.h>
using namespace std;using ll = long long;
const int maxn = 100010;
struct Edge {int v, w;
};
vector<Edge> G[maxn];
struct Node {int u;ll d;bool operator<(const Node &n) const { return d > n.d; }
};
ll d[maxn];
bool vis[maxn];void Dij(int s) {// 一定要初始化memset(d, 0x3f, sizeof(d));priority_queue<Node> pq;d[s] = 0, pq.push({s, d[s]});while (!pq.empty()) {int u = pq.top().u;pq.pop();// u 可以进入 pq 多次，只取第一次if (vis[u]) continue;vis[u] = 1;for (Edge e : G[u]) {int v = e.v, w = e.w;if (d[v] > d[u] + w) {d[v] = d[u] + w;pq.push({v, d[v]});}}}
}int main() {int n, m;cin >> n >> m;for (int i = 0; i < m; ++i) {int u, v, w;cin >> u >> v >> w;G[u].push_back({v, w});}Dij(1);for (int i = 1; i <= n; ++i) cout << d[i] << " ";return 0;
}

双端队列 BFS（01 BFS）

回顾普通队列 BFS 求最短路的算法特征

用于解决边权为 1 的单源最短路问题。
按照离起点”由近到远“的顺序搜索，即队列中越靠前的结点离起点是越近的（队列有单调性）。
每个结点第一次被访问到（被更新离起点的距离），就可以确定起点到它的最短路长度。即每个结点只入队一次，出队一次。

双端队列 BFS 类似

用于解决边权为 0 或 1 的单源最短路问题。
要像普通 BFS 一样保持队列的单调性。用 d[u] + w 更新 d[v] 时，如果边权 w 是 1，像普通队列一样将 v 入队到队尾，如果 w 是 0，那么 d[v] 与队头 u 的 d[u] 相同，v 应该入队到队头。
结点 v 可能被一条边 (u, v, 1) 更新，入队到队尾，接下来可能又被 (x, v, 0) 更新，入队到队头，所以一个结点最多可能入队 2 次，出队 2 次。
一个结点 u 第一次出队的时候就确定了最短路，扫描出边更新相邻结点，第二次出队再次扫描出边则是无用功。可以标记避免第二次扫描出边，不管也影响不大，多扫描一次只是时间上慢一点，时间复杂度仍然是 $O (n + m)$ 。

参考代码

const int maxn = 100010;
struct Edge {int v, w;
};
vector<Edge> G[maxn];
int d[maxn];
void bfs01(int s) {memset(d, 0x3f, sizeof(d));deque<Edge> q;q.push_back({s, d[s]}), d[s] = 0;while (!q.empty()) {int u = q.front().v;q.pop_front();for (Edge e : G[u]) {int v = e.v, w = e.w;if (d[v] > d[u] + w) {d[v] = d[u] + w;if (w == 0) q.push_front({v, d[v]});else q.push_back({v, d[v]});}}}
}

ch11 部分题目解法

逃离地下城

详见课本【例11.3】逃离地下城

邮差小图

知识点：最短路、Dijkstra 算法
思路：
- 题目本质上可以分成两个部分
  - 第一部分计算从 1 号节点到所有其他节点的最短路径和，可以对原图跑一次 dij 算法，计算出从 1 号节点到所有其他节点的最短路径，再求和即可。
  - 第二部分计算从所有其他节点到 1 号节点的最短路径和，其实等价于对原图反向建图，计算从 1 号节点到所有其他节点的最短路径和，同理反向建图后跑一次 dij 算法，即可得到答案。

数字变换

知识点：最短路、广度优先搜索
思路：
- 转换成图上去思考：
  - 可以将每个点看成图上的一个节点，每个节点 x 和 x + 1、x - 1 各有一条出边（前提是对应的 x + 1 和 x - 1 在 1 ~ n 范围内）
  - 特别地，如果 x 是某个 $a_i$ 的倍数，那么 x 和所有 $a_i$ 的倍数都有一条连接的边。
- 对该图求最短路，计算出从 1 号节点到 n 号节点的最短路径
  - 由于该图中，每条边的边权都是 1，因此可以直接通过广度优先搜索（bfs），计算到达每个点的最短路长度
  - 在处理到某个节点 x，如果 x 是某个 $a_i$ 的倍数，它需要遍历所有 $a_i$ 的倍数，去更新它们的答案，如果所有 $a_i$ 的倍数都如此操作一次，时间复杂度太高了，也没有必要，因为搜索的过程中，第一次到达某节点 x 时，即代价是 d[x]，那么所有 $a_i$ 的倍数除了 x 本身的代价就是 d[x] + 1，已经在第一次到达 x 时就确定了，后序无需在更新这些 $a_i$ 的倍数，也就无需再遍历了
    - 例如假设 n = 20， $a_i = 3$ ，假设第一次搜索到 6，那么就可以更新所有 3,9,12,15,18 的答案。如果搜索到 3, 9, 12, 15, 18 无需再把所有 3 的倍数遍历一次了
代码：

const int N = 2e6 + 5;
int n, k, a[15], d[N], vis[N], f[15]; //f[i] 标记第 i 个数的所有倍数是否被处理过void bfs(int s) {memset(d, 0x3f, sizeof(d));d[s] = 0;queue<int> q;q.push(s);while (!q.empty()) {int x = q.front();q.pop();if (vis[x])continue;vis[x] = 1;if (x - 1 >= 1 && d[x - 1] > d[x] + 1) {d[x - 1] = d[x] + 1;q.push(x - 1);}if (x + 1 <= n && d[x + 1] > d[x] + 1) {d[x + 1] = d[x] + 1;q.push(x + 1);}for (int i = 1; i <= k; i++) {//如果 ai 的倍数没有访问过，则访问if (!f[i] && x % a[i] == 0) {f[i] = 1; //标记，避免下次重复遍历for (int v = a[i]; v <= n; v += a[i]) {if (d[v] > d[x] + 1) {d[v] = d[x] + 1;q.push(v);}}}}}
}int main() {cin >> n >> k;for (int i = 1; i <= k; i++) cin >> a[i];bfs(1);cout << d[n];return 0;
}

「USACO 09OPEN」Hide and Seek

知识点：最短路、Dijkstra 算法
思路：
- 题目实际上求解的是从第一个谷仓出发，到其他谷仓最短距离中的最大值，以及编号
- 可以将每个谷仓视为图上的一个节点，通过 dij 算法计算出 1 号节点到达其他节点的最短路，再打擂台算出最短路的最大值，并求出编号即可。
代码

// ... 此处省略 dijkstra 代码
int main() {// ... 此处省略读入和存图dij(1);int Max = 0, u = 0, cnt = 0;//先算最短路的最大值for (int i = 1; i <= n; i++) {Max = max(Max, d[i]);}//再算最大值的最小编号，以及有几个最大值for (int i = 1; i <= n; i++) {if (d[i] == Max) {if (u == 0) u = i;cnt++;}}cout << u << " " << Max << " " << cnt << endl;return 0;
}