困难C++4 分钟1,255 字
单源次短路
次短路指从起点到终点的第二短路径长度(严格大于最短路)。它是最短路问题的经典变体,在 NOI 大纲提高级中列为【7】难度考点。
问题定义
给定带权图,起点 s,终点 t,求从 s 到 t 的次短路径长度。
有两种常见定义,题目会明确说明用哪种:
| 类型 | 要求 | 例:s→a→t 长 5,s→b→t 长 5 |
|---|---|---|
| 严格次短路 | 长度必须 大于 最短路 | 需找第 3 短的路径 |
| 非严格次短路 | 长度 ≥ 最短路即可,可相等 | 就是 5(换条路走) |
大多数题目要求严格次短路。
核心思路:维护两个距离
标准的 Dijkstra 只维护"到每个点的最短距离"。次短路需要再加一维:
dis[u][0] = 起点到 u 的最短距离
dis[u][1] = 起点到 u 的次短距离
每次用 (u, d, 类型) 去松弛邻居 v 时,尝试把 d + w 更新到 v 的这两个位置上。关键:同一个点可以被访问两次(一次作为最短路,一次作为次短路)。
代码实现
cpp
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Edge { int to, w; };
vector<Edge> g[100005];
int dis[100005][2]; // [点][0=最短路, 1=次短路]
void dijkstra(int s, int n) {
// 初始化
for (int i = 1; i <= n; i++)
dis[i][0] = dis[i][1] = INF;
// 小根堆:(距离, 点, 类型)
priority_queue<tuple<int, int, int>,
vector<tuple<int, int, int>>,
greater<>> pq;
dis[s][0] = 0;
pq.emplace(0, s, 0);
while (!pq.empty()) {
auto [d, u, t] = pq.top(); pq.pop();
// 过期判断:如果堆里的值已经比当前记录大,说明是旧数据
if (d > dis[u][t]) continue;
// 严格次短路:等于最短路的值不算进次短路
if (t == 1 && d == dis[u][0]) continue;
for (auto& e : g[u]) {
int v = e.to;
int nd = d + e.w;
if (nd < dis[v][0]) {
// 新的最短路:原来的最短路降级为次短路
dis[v][1] = dis[v][0];
dis[v][0] = nd;
pq.emplace(dis[v][1], v, 1);
pq.emplace(dis[v][0], v, 0);
} else if (nd > dis[v][0] && nd < dis[v][1]) {
// 介于最短路与次短路之间
dis[v][1] = nd;
pq.emplace(nd, v, 1);
}
// 注意:nd == dis[v][0] 时直接忽略(严格次短路)
}
}
}
为什么同一节点要入队两次
因为 dis[u][1] 也能作为次短路的"中转"进一步松弛别人。如果一个点只被当作"最短路节点"处理一次,就会漏掉经过次短路延伸的路径。
边界与细节
1. 严格 vs 非严格
上面代码里 else if (nd > dis[v][0] && nd < dis[v][1]) 的 > 保证严格。如果要非严格次短路,改成 nd >= dis[v][0]:
cpp
} else if (nd >= dis[v][0] && nd < dis[v][1]) {
dis[v][1] = nd;
...
}
2. 次短路不存在
如果图是树或单链,次短路可能不存在,此时 dis[t][1] 仍为 INF,需要特判输出 -1。
cpp
if (dis[t][1] == INF) cout << -1;
else cout << dis[t][1];
3. 无向图要建双向边
cpp
void addEdge(int u, int v, int w) {
g[u].push_back({v, w});
g[v].push_back({u, w});
}
另一种思路:Dijkstra 标准解法
也常见一种"把次短路也当状态"的写法,思路更统一:
cpp
void dijkstra2(int s, int n) {
fill(&dis[0][0], &dis[0][0] + 100005 * 2, INF);
priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;
dis[s][0] = 0;
pq.emplace(0, s, 0);
while (!pq.empty()) {
auto [d, u, t] = pq.top(); pq.pop();
if (d > dis[u][t]) continue;
for (auto& e : g[u]) {
int v = e.to, nd = d + e.w;
for (int k = 0; k < 2; k++) {
// 尝试把 nd 更新到 v 的第 k 类型上
if (nd < dis[v][k]) {
swap(nd, dis[v][k]); // 小的顶上去
pq.emplace(dis[v][k], v, k);
}
}
}
}
}
这段的精妙之处在于 swap:如果 nd 比 dis[v][k] 小,就先交换,让小的占据位置,然后把挤出来的旧值继续拿去尝试更新的那一维。
例题:给定期望的次短路
题目:n 点 m 边无向图,求 1 到 n 的严格次短路长度。
输入:
4 4
1 2 1
2 4 1
1 3 5
3 4 5
最短路:1→2→4,长度 2
次短路:1→3→4,长度 10
输出:10
cpp
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
addEdge(u, v, w);
}
dijkstra(1, n);
cout << (dis[n][1] == INF ? -1 : dis[n][1]) << endl;
}
与最短路的区别
| 项目 | 最短路 | 次短路 |
|---|---|---|
| 距离维度 | 1 维 dis[v] |
2 维 dis[v][0/1] |
| 每点入队次数 | 1 次 | 最多 2 次 |
| 松弛条件 | nd < dis[v] |
分别判断 0/1 两维 |
| 复杂度 | O((n+m)log n) | O((n+m)log n),常数略大 |
| 不存在的可能 | 可达即存在 | 可能不存在(退化图) |
常见错误
- **只更新
dis[v][0]**:忘记把旧的最短路降级为次短路,结果等于普通 Dijkstra。 - 非严格/严格搞混:题目要求严格次短路,却用
>=接受等长路径。 - 次短路不存在没特判:输出
INF而不是-1。 - 过期判断缺失:堆里同一个状态被重复加入,不判断
d > dis[u][t]会重复处理。 - 无向图只加单向边:结果可能比真实值大很多,甚至不通。
小结
次短路的本质是把"距离"从一维扩展成两维,让每个点保存最优和次优两个值。实现时注意三件事:严格性判断用 >、同一节点要入队两次、以及次短路可能不存在。掌握后,这类"第 k 短"的问题都可以用同样的多维度扩展思路解决。