最短路问题

概述

对于无权图（01 带权），可以使用 BFS 求解最短路。

对于多源最短路，可以使用 Floyd 算法，也就是通过 $n$ 轮 DP 来求解最短路。

对于单源最短路，可以使用 Dijkstra 和 SPFA。Dijkstra 基于贪心的思想，每次寻找当前最短的路来走，正确性基于边权非负；SPFA 则通过 $O(nm)$ 的迭代来更新最短路，进而可以判断负环的存在性。

Johnson 通过将边改造为 $(u,v,w+d_u-d_v)$ 来实现，边权是三角形不等式来满足 $\ge 0$，建立超级源点跑 SPFA 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <bits/stdc++.h>
using namespace std; 
typedef long long i64; 
const int N = 3e3 + 5; 
const int INF = 1e9; 

int n, m, cnt[N]; 
vector<pair<int, i64>> G[N]; 
i64 d[N], h[N]; 
bool vis[N], inq[N]; 

void Dijkstra(int s) {
    fill(d, d + n + 1, INF); memset(vis, 0, sizeof vis); 
    #define pil pair<int, i64>
    priority_queue<pil, vector<pil>, greater<pil>> q; 
    q.emplace(d[s] = 0, s); 
    while (!q.empty()) {
        int u = q.top().second; q.pop(); 
        if (vis[u]) continue; vis[u] = 1; 
        for (auto [v, w] : G[u]) if (d[v] > d[u] + w) q.emplace(d[v] = d[u] + w, v); 
    }
}

void SPFA(int s) {
    fill(d, d + n + 1, INF); d[s] = 0; 
    queue<int> q; q.push(s); inq[s] = 1; 
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for (auto [v, w] : G[u]) if (d[v] > d[u] + w) {
            d[v] = d[u] + w; cnt[v] = cnt[u] + 1; 
            if (cnt[v] > n + 1) cout << "-1\n", exit(0); 
            if (!inq[v]) q.push(v), inq[v] = 1; 
        }
    }
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m; 
    while (m--) {
        int u, v, w; cin >> u >> v >> w; 
        G[u].emplace_back(v, w); 
    }
    for (int i = 1; i <= n; ++i) G[0].emplace_back(i, 0); 
    SPFA(0); 
    for (int u = 1; u <= n; h[u] = d[u], ++u) for (auto& [v, w] : G[u]) w += d[u] - d[v]; 
    for (int i = 1; i <= n; ++i) {
        Dijkstra(i); i64 ans = 0; 
        for (int j = 1; j <= n; ++j) {
            if (d[j] == INF) ans += 1ll * j * INF; 
            else ans += j * (d[j] + h[j] - h[i]);
        }
        cout << ans << '\n'; 
    }
    return 0; 
}

如果我们要求的是最短简单路径（有负环），那么它是一个 NPC 问题。

差分约束

根据三角形不等式进行连边，然后用 SPFA 判断负环。

值得注意的是，如果使用 SPFA 求最短路，那么得到的是字典序最大的解。对于字典序最小的解，只需要将约束条件统统变为 $x_i-x_j\ge y$，然后跑最长路，有正环时无解（就是边的方向和权值都取反）。

[省选联考 2021 A 卷] 矩阵游戏。答案的构造是容易的，然后需要调整这个答案，让每一行和列依次 $+1,-1$，然后错开，直接差分约束即可。代码。

斯坦纳树

如果给定 $n$ 个点，试求连接此 $n$ 个点，总长最短的直线段连接系统，并且并且任意两点都可以通过系统中的直线段组成的折线连接起来，此问题被称为斯坦纳树问题。遗憾的是，这是一个 NPH 问题。

并不是直接将 $S$ 连接起来就是最小的，可能需要借助剩下的 $n-k$ 个点。这种问题可以使用状压 DP 来解决：

设 $f(i,S)$ 表示以 $i$ 为根的一棵树，包含集合 $S$ 中所有点的最小边权值和。有转移：$f(i,S)\leftarrow\min\{f(i,T)+f(i,S-T)\},f(i,S)\leftarrow\min\{f(j,S)+w(i,j)\}$。前者可以使用子集 DP 实现，后者可以跑一个最短路（由于图很难特殊构造而且规模很小，所以实际上更建议 SPFA）。代码。

Peach Blossom Spring，注意并不要求完全联通，最后子集和并一下即可。

平面图最小割

如果图 $G$ 能画在平面 $S$ 上，即除顶点处外无边相交，则称 $G$ 可平面嵌入 $S$，$G$ 为可平面图或平面图。画出的没有边相交的图称为 $G$ 的平面表示或平面嵌入。

平面图可以转为对偶图，对偶图的最短路等于原平面图的最小割。给 $G$ 的每个面搞一个点，两个面的公共边可以确定一条与其方向垂直的边。给源点和汇点连线可以将原图分成两个部分，跑最短路即可。

注意左侧和下侧，上侧和右侧分别是同一个点，从右上到左下的最短路即为左上到右下的最小割。模板，代码。

同余最短路

模板。这是一个最短路的变式问题。可以用于求解在某个范围内有多少重量可以由若干物品的完全背包凑出，就是多少数值可以由一些给定的数 $b_i$ 由 $\sum a_i b_i(a_i\ge 0)$ 得到。

我们可以发现，如果 $x$ 可以被表示出，那么 $x+ka_i(k>0)$ 就可以被表示出。因此我们找一个最小的 $a_1$，然后连 $j\rightarrow (j+a_i)\bmod a_1$ 的长度为 $a_i$ 的边，然后我们从 $0$ 开始跑最短路。由于这里图的形态不太能特殊构造，因此使用 SPFA 往往会跑的更快。最后求出的 $f_i$ 代表最小的能被凑出的数，满足 $f_i\bmod a_1 =i$。代码。

答案的求解十分容易。$[0,r]$ 的答案数量为：

$$\sum_{i=0}^{a_1-1}\max\left\{0,\left\lfloor\frac{r-f_i}{a_1}\right\rfloor+1\right\}$$

但为什么要使用最短路呢？实际上这东西是体积模 $m$ 意义下的完全背包，如果重复经过一个点，那么可以选择 $\frac{m}{\gcd(v_i,m)}-1$ 个这类物品。也就是说，会在大小为 $m$ 的环上形成 $\gcd(v_i,m)$ 个子环。

那么在每个子环上转两圈即可统计到所有转移，时间复杂度 $O(nm)$。代码。

如果我们将密度最大的物品选做基准物品，那么其它物品的选择可以替换为若干基准物品，这样可以最大化贡献。设基准物品体积为 $w$，贡献为 $m$。

设 $f_i$ 代表最大的贡献，满足 $V\bmod m=i$。最终权值为 $f_i+\frac{V-V'}{m}w$，因此要最大化 $V-\frac{V'}{m}$，因此贡献应该是 $f_p+c_i-\frac{p+v_i}{m}w$。

可以发现每个 $f_i$ 对应的物品个数一定是不超过 $v$ 的，因此这一部分总容积不超过 $v^2\le V$，不存在误判成有解的情况。代码。

删边最短路

求出 $1,n$ 的最短路树 $T_1,T_n$。如果改的边不是最短路上的边的答案是好算的，否则，我们要算出强制不经过一条边的新的最短路。

我们可以证明，一定可以枚举一条边 $(u,v)$，然后 $1\rightarrow u,v\rightarrow n$ 走的都是最短路。

我们需要保证 $T_1,T_n$ 上 $1\sim n$ 的最短路是相同的一条，否则无法计算。

求出 $p1_i$ 代表 $T_1(1\rightarrow i)$ 与更新路径的最后一个交点（在最短路树上跳，第一个到的最短路上的点，就是 $i$ 与 $n$ 的 LCA），$pn_i$ 同理。

这样维护先修改再单点查询的区间 ckmin 即可。代码。

显然，这种做法并不能在有向图上成立，因为不在最短路上的边可能不止一条。但是，走的路径依然满足中间只有一段不在最短路上的路径。

k 短路

先建出一棵以 $t$ 为根的最短路树 $T$，$x$ 到 $t$ 的最短路径为 $d_x$。设 $s\rightarrow t$ 的路径上不在 $T$ 中的当前选择的路径的边集为 $P'$，$s\rightarrow t$ 上的所有边为 $P$，那么满足：

1. 将一条边 $e$ 的代价定义为 $\Delta e = w-(d_u-d_v)$，那么 $L_{P'} = d_s + \sum_{e\in P'} \Delta e$；
2. 将 $P$ 和 $P'$ 中所有边按照 $s\rightarrow t$ 经过的顺序依次排列，那么对于 $P'$ 中相邻的边 $e_1,e_2$，那么 $v_{e_1}=u_{e_2}$ 或者 $u_{e_2}$ 是 $v_{e_1}$ 在 $T$ 上的祖先。
3. 对于每一个合法的 $P'$，有且仅有一个 $P$ 与之对应。因为可以根据 $P'$ 还原在 $T$ 上选择了什么。

也就是说，我们现在要求满足性质 $2$ 的第 $k$ 小 $L_p$。

我们记录最后一条边和当前 $L_p$ 的值即可表示 $P'$。初始我们将 $1$ 所有在 $T$ 上的祖先的所有的边中 $\Delta e$ 最小的一条边加入小根堆，然后扩展时只有两种选择：

1. 删掉 $P'$ 结尾的那条边，换成第二大的边；
2. 从 $P'$ 的结尾开始到 $T$ 的路径上，选择最小的边加入。

已知我们开始的描述路径的方式是不漏的，而且我们相当于枚举了所有的待替换边是否进行替换，因此这么做是正确的。

时间复杂度 $O(m\log m+k\log k)$，模板，代码。

$k$ 短路问题能够高效解决，得益于我们只需要一个点即可描述能够被替换的边，如果要输出 $k$ 短路的方案，那么就只能做到 $O(k(n+m)\log m+k\log k)$ 了。

例题

刷基础 I

[Shenyang Regional 2025] The Bond Beyond Time

Portal。$x,y$ 不相邻是容易解决的。相邻时需要将两个点引到一个环上转圈，因此需要求最小环。数据范围很小，因此直接暴力删边求最短路以求最小环即可。代码。

[ZJCPC2025] Challenge NPC III

Portal。相当于与是同色点之间的最短路应该大于 $k$，于是对每个颜色都跑多起点最短路，在反图上也跑一遍，就可以求出距离，需要记录次短路防止起点终点相同。代码。

刷综合

[THUSCH2017] 巧克力

Portal.

如果颜色数比较少的话直接用斯坦纳树做，但是颜色数很多，钦定的可能也很多。

$k$ 很小，因此考虑将所有颜色随机映射到 $[0,k)$，然后求最小斯坦纳树即可求出最小的巧克力个数 $w$。这 $k$ 个点被分配到不同的颜色时答案合法，正确概率是 $k!/k^k$。随机化做 $200$ 次即可。

然后二分出中位数，将小于等于二分值的权值都设为 $inf-1$，大于的都设为 $inf+1$，然后最小斯坦纳树要 $\le w\times inf$（$inf$ 设置为一个不会影响斯坦纳树选择的巧克力数的一个数即可）。代码。