最短路算法 (Shortest Paths)¶
最短路径算法是图论竞赛题目中的基石。根据边权特性（非负权、负权、任意权）及查询类型（单源、多源/全源），选用合适的算法。
堆优化 Dijkstra 算法 (单源非负权)¶
适用于边权非负的有向图或无向图。时间复杂度为 \(\mathcal{O}((V + E) \log V)\)。
#include <vector>
#include <queue>
struct Edge {
int to;
long long weight;
};
// 返回从 source 出发到所有顶点的最短路距离
std::vector<long long> dijkstra(int n, int source, const std::vector<std::vector<Edge>> &adj) {
constexpr long long INF = 0x3f3f3f3f3f3f3f3fLL;
std::vector<long long> dist(n + 1, INF);
// 小顶堆: pair<距离, 节点编号>
std::priority_queue<std::pair<long long, int>,
std::vector<std::pair<long long, int>>,
std::greater<std::pair<long long, int>>> pq;
dist[source] = 0;
pq.push({0, source});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue; // 懒惰删除已失效状态
for (const auto &e : adj[u]) {
if (dist[u] + e.weight < dist[e.to]) {
dist[e.to] = dist[u] + e.weight;
pq.push({dist[e.to], e.to});
}
}
}
return dist;
}
SPFA 算法 (含负权边与负环检测)¶
队列优化的 Bellman-Ford 算法。适用于存在负权边或判断图中是否存在负环的场景。最坏时间复杂度 \(\mathcal{O}(VE)\)，在随机图上表现优秀（网格图或特殊构造卡常图慎用）。
#include <vector>
#include <queue>
// 返回是否存在负环。若无负环，dist 数组存储从 source 出发的最短距离
bool spfa(int n, int source, const std::vector<std::vector<Edge>> &adj, std::vector<long long> &dist) {
constexpr long long INF = 0x3f3f3f3f3f3f3f3fLL;
dist.assign(n + 1, INF);
std::vector<int> cnt(n + 1, 0); // 记录入队次数或松弛边数
std::vector<bool> in_queue(n + 1, false);
std::queue<int> q;
dist[source] = 0;
q.push(source);
in_queue[source] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
in_queue[u] = false;
for (const auto &e : adj[u]) {
if (dist[u] + e.weight < dist[e.to]) {
dist[e.to] = dist[u] + e.weight;
cnt[e.to] = cnt[u] + 1;
if (cnt[e.to] >= n) {
return true; // 存在负环
}
if (!in_queue[e.to]) {
q.push(e.to);
in_queue[e.to] = true;
}
}
}
}
return false;
}
Floyd-Warshall 算法 (全源最短路)¶
基于动态规划求解任意两点间的最短路径，支持负权边。时间复杂度 \(\mathcal{O}(V^3)\)。
#include <vector>
#include <algorithm>
void floyd(int n, std::vector<std::vector<long long>> &d) {
// d[i][i] = 0, 其余根据边初始化为权值或 INF
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (d[i][k] != 0x3f3f3f3f3f3f3f3fLL && d[k][j] != 0x3f3f3f3f3f3f3f3fLL) {
d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
}
经典题型模型与高频技巧¶
-
分层图 / 多维状态图 Dijkstra：
- 将图中的状态由单点 \(u\) 扩展为多元组 \((u, \text{state})\)，例如 \((u, \text{优惠券数})\)、\((u, \text{油量})\) 或 \((u, \text{步数奇偶性})\)。
- 状态层级间的转移对应特定规则的操作（如边权减半、边权置零或改变方向）。
-
同余最短路：
- 求解形如 \(\sum a_i x_i \le K\) 的完全背包/正整数线性组合问题时，选取最小元素 \(a_0 = m\) 作为模数。
- 设 \(dist[r]\) 表示模 \(m\) 余 \(r\) 的最小可达数。建立同余图：\(u \xrightarrow{a_i} (u + a_i) \bmod m\)，边权为 \(a_i\)，运行 Dijkstra。
- 满足 \(\le K\) 的方案总数为 \(\sum_{r=0}^{m-1} \max(0LL, \lfloor (K - dist[r]) / m \rfloor + 1)\)。
-
最短路树 (SPT) 与子图保留：
- Dijkstra 每次对节点 \(v\) 进行严格松弛的前驱边记录为 \(p[v]\)，构成以源点为根的最短路有向树/DAG。
- 广泛用于保留特定数量边且维持最短路不变的删边与保留问题。
-
0-1 分数规划结合 SPFA 判负环：
- 针对最优化比值 \(\frac{\sum f_i}{\sum w_i} \ge \lambda\) 的问题，变形为 \(\sum (\lambda w_i - f_i) \le 0\)。
- 赋予有向边权值 \(w'(u, v) = \lambda w_e - f_u\)，使用全源入队的 SPFA 检验图中是否存在负环以调整二分上下界。
-
逆序增量 Floyd-Warshall：
- 当题目要求依次删除节点并动态求全源最短路和时，逆序反转操作序列，将“删点”变为“加点”，每次将新加入的点作为中间松弛点 \(k\)，在 \(\mathcal{O}(V^2)\) 内增量更新距离矩阵。
经典推荐习题¶
-
提示
堆优化 Dijkstra 模板。由于边权可达 \(10^6\) 且 \(N \le 10^5\)，距离数组必须使用
long long防止整型溢出。维护一个parent[v]数组，每次严格松弛更新时记录前驱。若dist[n] == INF输出-1；否则从 \(n\) 沿parent回溯至 1，翻转序列即可输出完整最短路径。 -
Codeforces 1076D - Edge Deletion
提示
从源点 1 出发的最短路构成一棵至多包含 \(n-1\) 条边的最短路树（SPT）。运行 Dijkstra，记录每个非源点点 \(v\) 达到最短距离时的最后一条转移边编号。建出 SPT 后，从根节点 1 开始运行 BFS，按遍历顺序选取前 \(\min(k, n-1)\) 条树边。树上 BFS 序能严格保证所选边的导出子图连通且包含源点。
-
Codeforces 295B - Greg and Graph
提示
逆序处理查询：从空图开始，按照删点的逆序依次激活节点。在第 \(t\) 步激活节点 \(x_t\) 时，将 \(x_t\) 视为 Floyd-Warshall 的中间转移点 \(k = x_t\)，在 \(\mathcal{O}(V^2)\) 时间内更新所有已激活点对间的距离 \(d[i][j] = \min(d[i][j], d[i][x_t] + d[x_t][j])\)。统计当前所有激活点对的最短距离之和，最后翻转答案数组输出。
-
Codeforces 1473E - Minimum Path
提示
路径权值目标为 \(\sum w_e - \max w_e + \min w_e\)，相当于必须选择恰好一条边费用为 0（免单），且选择恰好一条边费用为 \(2w\)（翻倍）。构建 4 层分层图，状态定义为 \((u, \text{used\_discount}, \text{used\_double})\)，每个标记为 0 或 1。每条原图有向边对应 4 种转移：普通边 \((w)\)、免单边 \((0)\)、翻倍边 \((2w)\)、以及在同一条边上同时免单且翻倍 \((w)\)。从 \((1, 0, 0)\) 出发跑单源 Dijkstra，答案即为各终点在 \((i, 1, 1)\) 状态下的距离。
-
Codeforces 1442C - Graph Transversals
提示
第 \(k\) 次全局边翻转耗费 \(2^k\)，而走一步原图边仅耗费 1。
- 翻转次数较少时（\(k < 20\)）：翻转代价 \(2^{19} \approx 5.2 \times 10^5\) 与路径长度在同一量级，在状态空间 \((u, k)\) 上直接跑 Dijkstra。
- 翻转次数较大时（\(k \ge 20\)）：多翻转一次的代价 \(2^{20} > 2 \times 10^5\) 严格超过全图走边的最大可能步数，因此极小化翻转次数 \(k\) 拥有绝对最高优先级。在 2 状态分层图 \((u, k \bmod 2)\) 上跑字典序双权值 \((k, \text{steps})\) 的 0-1 BFS / Dijkstra 即可。
-
AtCoder ABC 252 E - Road Reduction
提示
以点 1 为源点跑
long long堆优化 Dijkstra。对每个点 \(v \in [2, N]\)，记录使其严格更新最短距离的最优边编号。这 \(N-1\) 条边构成一棵最优最短路树（SPT），完美保留了从点 1 到所有点的最短距离。 -
AtCoder ABC 061 D - Score Attack
提示
将所有边权取反（\(w'_e = -c_e\)），将求最大得分转化为求点 1 到点 \(N\) 的最短路。从源点 1 运行 Bellman-Ford 算法 \(N\) 轮松弛。第 \(N\) 轮仍能被成功松弛的点说明处于或受负环影响。关键避坑点：只有当这些负环能够到达终点 \(N\) 时，得分才会无限增大输出
inf。因此，从第 \(N\) 轮被松弛的所有点出发运行一次 BFS/DFS，若终点 \(N\) 可达则输出inf，否则答案为 \(-dist[N]\)。 -
AtCoder ABC 243 E - Edge Deletion
提示
运行 \(\mathcal{O}(N^3)\) 的 Floyd-Warshall 求出全源最短路矩阵 \(d[u][v]\)。一条原图边 \((u, v)\)（权值 \(w\)）可以被安全删除当且仅当存在第三个中继点 \(k \notin \{u, v\}\) 满足 \(d[u][k] + d[k][v] \le w\)（即使相等，经过 \(k\) 的路径至少包含 2 条边，直连边同样冗余）。在 \(\mathcal{O}(M \cdot N)\) 时间内检验每条边即可。
-
提示
从点 1 到 \(u\) 的总快乐值为 \((H_1 - H_u) - \sum \text{损失}\)。滑行时若 \(H_u \ge H_v\) 损失为 0；若 \(H_u < H_v\) 损失为 \(H_v - H_u\)。所有损失值均非负！因此为每条滑道的两个方向赋予非负有向边权 \(w(u, v) = \max(0, H_v - H_u) \ge 0\)。从点 1 运行标准 Dijkstra 求出到达每个点的最小总损失 \(dist[u]\)，终点 \(u\) 的最大快乐值即为 \((H_1 - H_u) - dist[u]\)，取全局最大值即可。
-
AtCoder ABC 164 E - Two Currencies
提示
在任意无环简单路径上所需的银币上限不超过 \((N - 1) \times \max(A_i) \le 49 \times 50 < 2500\)。将银币持有量截断在 \(S_{\max} = 2500\)。建立 2D 状态空间 \((u, s)\)，其中 \(u \in [1, N]\)，\(s \in [0, 2500]\)（总状态数约 \(1.25 \times 10^5\)）。转移分为两类：乘车前往相邻城市（消耗银币 \(A\)，耗时 \(B\)）与在当前城市用金币兑换银币（增加银币 \(C\)，耗时 \(D\)）。从 \((1, \min(2500, S))\) 出发跑 Dijkstra 即可。
-
USACO 2014 Dec Silver - Piggy Back
提示
无权图最短路，直接使用 BFS。分别以 1 号谷仓、2 号谷仓和 \(N\) 号谷仓为源点运行三次独立的 BFS，分别计算出各点到它们的距离 \(d_1, d_2, d_N\)。枚举两头牛汇合的谷仓编号 \(k \in [1, N]\)，总能量消耗为 \(B \cdot d_1[k] + E \cdot d_2[k] + P \cdot d_N[k]\)，取最小值即可。
-
USACO 2018 Dec Gold - Fine Dining
提示
首先从 \(N\) 出发跑一次单源 Dijkstra，求出各牧场直接到 \(N\) 的基础最短路 \(dist_N[u]\)。一头牛在牧场 \(u\) 能够中途品尝干草捆 \(p\)（美味度 \(y_p\)）且不超时，当且仅当：
\[ \min_p \big( dist(u, p) + dist_N[p] - y_p \big) \le dist_N[u] \]多源 Dijkstra 技巧：将所有干草捆所在的牧场 \(p\) 一同入队作为多源起点，初始距离设为 \(dist_N[p] - y_p\)。运行 Dijkstra 求出各牧场的进食最短距离 \(dist_{\text{dine}}[u]\)，若 \(dist_{\text{dine}}[u] \le dist_N[u]\) 则输出 1，否则输出 0。
-
USACO 2019 Dec Gold - Milk Pumping
提示
管道数 \(M \le 1000\)，候选瓶颈流量至多只有 \(M\) 种。枚举每条管道的流量 \(F\) 作为整条路径的瓶颈。对于每个候选 \(F\)，过滤出所有容量 \(f_e \ge F\) 的边构成子图，以花费 \(c_e\) 为边权在子图上跑 Dijkstra 求出 1 到 \(N\) 的最小花费 \(C\)。若可达则更新比值 \(\frac{F}{C}\)，最终输出 \(\lfloor 10^6 \cdot \max(F/C) \rfloor\)。
-
USACO 2007 Dec Gold - Sightseeing Cows
提示
0-1 分数规划典型题：二分最优比率 \(\lambda\)。条件 \(\frac{\sum F}{\sum T} \ge \lambda\) 等价于 \(\sum (\lambda T_e - F_u) \le 0\)。为每条有向边赋予边权 \(w(u, v) = \lambda T(u, v) - F_u\)。问题转化为判定图中是否存在非正环/负环。将所有点作为源点加入 SPFA 队列检验负环，若存在负环则说明 \(\lambda\) 可行，增大二分下界。
-
提示
同余最短路经典模型：选取集合中最小元素 \(a_1\) 作为模数。设 \(dist[r]\) 表示使用集合 \(A\) 中元素能拼出的模 \(a_1\) 余 \(r\) 的最小整数。在剩余系节点 \(\{0, 1, \dots, a_1 - 1\}\) 上建图，对所有 \(a_i \in A\) 连有向边 \(u \xrightarrow{a_i} (u + a_i) \bmod a_1\)，边权为 \(a_i\)。从源点 0 出发跑单源 Dijkstra（\(dist[0] = 0\)）。对于每个询问 \(q\)，可表示出的充要条件为 \(dist[q \bmod a_1] \le q\)。
-
POI 2013 - Task Tales of seafaring (mor)
提示
若 \(s\) 到 \(t\) 存在长为 \(L\) 的路径，只要 \(s\) 有相邻出边（\(\deg(s) > 0\)），在相邻边上来回走即可构造出长度为 \(L + 2k\) 的任意游走。因此只需记录偶数长度最短路 \(dist[s][t][0]\) 与奇数长度最短路 \(dist[s][t][1]\)。
- 从每个点 \(s\) 出发在 2 状态图 \((u, \text{奇偶性})\) 上运行 BFS，总耗时 \(\mathcal{O}(N(N + M))\)。
- 针对询问 \((s, t, d)\)：若 \(d = 0\)，当且仅当 \(s = t\) 输出 YES；若 \(d > 0\) 且 \(\deg(s) == 0\) 输出 NO；其余情况下只要 \(dist[s][t][d \bmod 2] \le d\) 即可输出 YES。
-
提示
从源点 1 运行 Dijkstra 计算各点最短距离，在松弛过程中同步维护四组 DP 值：
dist[u]：最短航线价格；count[u]：最短航线数量（模 \(10^9 + 7\)）；min_flights[u]：最短航线包含的最少航班数；-
max_flights[u]：最短航线包含的最多航班数。 对边 \(u \xrightarrow{w} v\) 松弛时： -
若
dist[u] + w < dist[v]：重置dist[v] = dist[u] + w，count[v] = count[u]，min_flights[v] = min_flights[u] + 1，max_flights[v] = max_flights[u] + 1。 - 若
dist[u] + w == dist[v]：累加count[v] = (count[v] + count[u]) % MOD，并更新min_flights[v] = min(min_flights[v], min_flights[u] + 1)，max_flights[v] = max(max_flights[v], max_flights[u] + 1)。
-
提示
单条边的路径长度就是边权本身。题目仅查询全图所有点对间的第 \(k\) 短路（\(k \le 400\)），因此该路径绝不可能包含任何比全图第 \(k\) 小边更重的边。
- 将全图所有边按边权升序排序，只保留前 \(\min(M, k)\) 条最轻的边。
- 这 \(\le k\) 条边至多涉及 \(2k \le 800\) 个不同顶点。
- 对涉及的有效顶点离散化，在导出的紧凑图上运行全源 Floyd-Warshall，耗时仅 \(\mathcal{O}((2k)^3)\)。
- 收集所有无向点对的最短距离排序，第 \(k\) 小即为最终答案。
LeetCode 经典真题精选与题解提示¶
-
LeetCode 743 - 网络延迟时间 (Network Delay Time)
中等提示
单源最短路径 Dijkstra 模板题。
- 从给定节点 \(k\) 出发，运行标准小顶堆优化的 Dijkstra 算法，计算出到全图其余所有点的最短路 \(dist[v]\)。
- 遍历所有节点：若存在无法到达的节点（\(dist[v] = \infty\)）则返回 \(-1\)；否则所有节点接收到信号的时间为 \(\max_{v} dist[v]\)。
-
LeetCode 787 - K 站中转内最便宜的航班 (Cheapest Flights Within K Stops)
中等提示
限定边数的最短路 (Bellman-Ford / 分层图)。
- 最多中转 \(k\) 次即最多允许走 \(k + 1\) 条边。
- 运行 Bellman-Ford 算法 \(k + 1\) 轮松弛。注意：每轮松弛必须基于上一轮结束时的距离副本（
clone数组）进行，防止在同一步内连续松弛多条边发生串联。
-
提示
全源最短路径 Floyd-Warshall 模板。
- 城市数量 \(n \le 100\)，规模极小，直接运行三重循环的 Floyd-Warshall 算法在 \(\mathcal{O}(n^3)\) 时间内计算出两两之间的全源最短距离矩阵 \(d[i][j]\)。
- 统计每个城市在阈值 \(distanceThreshold\) 内的到达城市数量，挑选数量最少者；若有平局，挑选编号最大的城市。
-
LeetCode 1514 - 概率最大的路径 (Path with Maximum Probability)
中等提示
变种 Dijkstra (最大乘积路径)。
- 边权为 \([0, 1]\) 之间的概率，路径综合概率为乘积。因为边权乘积单调不增，满足贪心性质。
- 使用大顶堆维护当前最大到达概率。松弛条件改为：若 \(prob[v] < prob[u] \times w\)，则更新 \(prob[v]\) 并将 \((prob[v], v)\) 入堆。
-
LeetCode 1976 - 到达目的地的方案数 (Number of Ways to Arrive at Destination)
中等提示
最短路计数与动态规划。
- 使用 Dijkstra 算法，同时维护最短耗时
dist[u]和到达 \(u\) 的最短路径方案数count[u]（模 \(10^9 + 7\)）。 - 当发现更短路径（
dist[u] + w < dist[v]）时：重置dist[v] = dist[u] + w，且count[v] = count[u]； - 当发现相同长度的最短路径（
dist[u] + w == dist[v]）时：累加计数count[v] = (count[v] + count[u]) % MOD。
- 使用 Dijkstra 算法，同时维护最短耗时