困难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 短"的问题都可以用同样的多维度扩展思路解决。

同类知识点