形式化题目

给定 $N$ 个结点、$R$ 条边的无向带权图 $G = (V, E)$，每条边权均为正整数；结点 $1$ 为起点，结点 $N$ 为终点。路径允许重复经过同一条边（考虑 walk，不要求简单）。

记 $S$ 为从 $1$ 到 $N$ 的所有路径中的最小长度，要求计算

即长度严格大于最短路、又不大于其他一切非最短路径的第二小长度。第二短路与最短路可以共用任意多条边，同一条边也可以被重复走多次；若有多条路径并列最短，它们只算同一个长度值，都必须被跳过。

样例：$4$ 个结点、$4$ 条边，边权见下图；最短路 $1 \to 2 \to 4$ 长 $100 + 200 = 300$，第二短路 $1 \to 2 \to 3 \to 4$ 长 $100 + 250 + 100 = 450$。

flowchart LR
    N1((1)) -->|100| N2((2))
    N2 -->|200| N4((4))
    N2 -->|250| N3((3))
    N3 -->|100| N4
    linkStyle 0 stroke-width:3px;
    linkStyle 1 stroke:#e5484d,stroke-width:3px;
    linkStyle 2 stroke:#3b82f6,stroke-width:3px;
    linkStyle 3 stroke:#3b82f6,stroke-width:3px;

红色的 $1 \to 2 \to 4$ 是最短路，蓝色的 $2 \to 3 \to 4$ 是第二短路绕开边 $(2, 4)$ 后的替代段，加粗的 $1 \to 2$ 则是两条路共用的开头。观察重点：第二短路并不是"完全不走最短路的边"，它只是把其中一段换成替代走法；任何绕圈的走法（如 $1 \to 2 \to 4 \to 2 \to 4$）都因边权为正而更长，不可能插到 $450$ 前面。

正解

思路

朴素做法及其瓶颈。 最直接的想法是 DFS 枚举所有路径再逐条比较长度，但路径条数是指数级，且允许重复走边后甚至无穷，$N = 5000$ 下完全不可行。另一个想法是先跑一次 Dijkstra 求出 $S$ 再想办法找"稍长一点"的路——瓶颈在于普通 Dijkstra 每个结点只记一个距离标签：当一条长度介于 $S$ 与次短之间的路到达时，它既不优于该标签，又正是我们要的答案，单标签只能把它丢掉。若改为对每个结点各跑一次单源最短路，复杂度 $O(N \cdot R \log R)$，在 $N = 5000,\ R = 10^5$ 下约 $5 \times 10^8 \times \log R \approx 10^{10}$ 次运算，也会超时。

关键观察（双标签引理）。 把每个结点的距离标签从一个扩成两个：best[v][0] 记最短、best[v][1] 记次短（严格递增，未发现为 $\infty$）。这样做的充分性来自一个引理：

设 $P^*$ 是到结点 $v$ 的第二短路，长度 $L^*$，去掉最后一条边 $(u, v, w)$ 得到前缀，长度 $p = L^* - w$。则 $p$ 一定是 $u$ 的最短或次短标签值。

反证：若 $p$ 大于 $u$ 的次短标签 $s_u$，则 $s_u + w$ 本身也是一条 $1 \to v$ 的真实路径，$s_u + w < p + w = L^*$。它不可能等于 $S$——否则 $u$ 的最短标签 $+ w \leqslant s_u + w = S$，而它作为一条 $1 \to v$ 的路径又有 $\geqslant S$，夹出 $u$ 的最短 = 次短，与严格递增矛盾。于是 $S < s_u + w < L^*$，与 $L^*$ 是第二短矛盾。同理可证最短路的前缀一定是 $u$ 的最短标签。结论：只要展开每个结点的前两个标签，就不会漏掉任何最短/次短候选。

双标签 Dijkstra。 于是算法水到渠成：小根堆按长度弹出 $(\text{length}, v)$，对每条出边 $(v, \text{nxt}, w)$ 计算候选 $\text{cand} = \text{length} + w$，按下表分三段处理：

两条配套规则缺一不可：

• 不设 visited 封印：题面允许重复走边；边权全为正，标签只会严格递减地刷新，且等于槽位值的候选被开区间拒绝，因此每个值只入堆一次，不会死循环；
• 过期项跳过：弹出时若 length > best[v][1]，说明这条值入堆后已被更小的次短淘汰，直接丢弃，避免用陈旧长度污染邻居。

下表按堆的弹出顺序，展示样例上 best[2]、best[3]、best[4] 三个结点的槽位刷新过程（每格写成 最短 / 次短，— 表示尚未发现）：

观察两点：其一，$(200, 1)$ 这一步是"允许走回头路"的直接体现——标签 200 是 $1 \to 2 \to 1$ 绕一圈的产物，它让 2 得到次短 300；其二，次短槽位不是一次定型的：4 的次短先记 500，随后被更小的 450 迭代刷新，最终 best[4] = 300 / 450，次短 450 即答案。这也说明每个结点的两个槽位各自只会严格递减地更新，总更新次数有限。

代码

Python 版：

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 14:44
# update_at: 2026-09-30 14:44

import heapq
import sys

INF = 10**18  # 未发现的长度哨兵：最长简单路远小于此


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    farm_cnt, road_cnt = next(data), next(data)

    road: list[list[tuple[int, int]]] = [[] for _ in range(farm_cnt + 1)]  # 2R 条有向邻接
    for _ in range(road_cnt):
        a, b, d = next(data), next(data), next(data)
        road[a].append((b, d))
        road[b].append((a, d))

    # 每个农场保留"最短 + 次短"两个长度；第二短路允许重复走边，所以松弛不禁止回头，
    # 只要求候选值严格落在 (最短, 次短) 开区间内才登记为新的次短。
    best = [[INF, INF] for _ in range(farm_cnt + 1)]
    best[1][0] = 0
    heap = [(0, 1)]  # (从农场 1 走到的长度, 农场编号)
    while heap:
        length, v = heapq.heappop(heap)
        if length > best[v][1]:  # 期间已登记更小的次短，堆里这条是过期项
            continue
        for nxt, w in road[v]:
            cand = length + w
            if cand < best[nxt][0]:  # 刷新最短：原最短自动降级为次短
                best[nxt][1] = best[nxt][0]
                best[nxt][0] = cand
                heapq.heappush(heap, (cand, nxt))
            elif best[nxt][0] < cand < best[nxt][1]:  # 严格更长但不超过现次短
                best[nxt][1] = cand
                heapq.heappush(heap, (cand, nxt))

    print(best[farm_cnt][1])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 04:33
 * update_at: 2026-10-05 04:33
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 5005;      // 结点数上限
const int MAXM = 400005;    // 边数上限（无向边存两条，2 * 10^5 * 2）
const ll INF = 1e18;

ll n, m;                    // 结点数 N、边数 R
ll best[MAXN][2];           // best[v][0] 最短距离，best[v][1] 次短距离（严格大于最短）

// 链式前向星存图（边权需要保存，单独开 w 数组）
int head[MAXN], nxt[MAXM], to[MAXM], edge_cnt;
ll w[MAXM];

// 加一条无向边。
void add_edge(int u, int v, ll d) {
    edge_cnt++;
    to[edge_cnt] = v;
    w[edge_cnt] = d;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 双标签 Dijkstra：小根堆按长度弹出，对每个结点同时维护最短与次短两个槽位。
void solve() {
    // 初始化两个槽位都是无穷大
    for (int i = 1; i <= n; i++) {
        best[i][0] = INF;
        best[i][1] = INF;
    }
    best[1][0] = 0;

    // 小根堆存 (长度, 结点)
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
    pq.push(make_pair(0LL, 1));

    while (!pq.empty()) {
        pair<ll, int> top = pq.top();
        pq.pop();
        ll length = top.first;
        int u = top.second;

        // 过期项跳过：这条长度入堆后已被更小的次短淘汰
        if (length > best[u][1]) continue;

        // 松弛 u 的每条出边
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            ll cand = length + w[i];
            if (cand < best[v][0]) {
                // 原最短降级为次短，cand 成为新最短
                best[v][1] = best[v][0];
                best[v][0] = cand;
                pq.push(make_pair(cand, v));
            } else if (cand > best[v][0] && cand < best[v][1]) {
                // 严格落在开区间 (最短, 次短) 内，才登记为次短
                best[v][1] = cand;
                pq.push(make_pair(cand, v));
            }
            // 其余情况丢弃：等于最短不算（要求严格大于），超过已知次短无意义
        }
    }

    cout << best[n][1] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        ll d;
        cin >> a >> b >> d;
        add_edge(a, b, d);
        add_edge(b, a, d);
    }

    solve();

    return 0;
}

复杂度

• 时间复杂度：建图遍历 $2R$ 条有向边耗时 $O(N + R)$；主循环中每个结点的两个槽位各刷新入堆常数次，堆元素总数 $O(N + R)$，每次堆操作 $O(\log R)$，整体 $O((N + R) \log R)$，与普通堆优化 Dijkstra 同阶。$N = 5000,\ R = 10^5$ 时约为 $10^6$ 量级的堆操作，全部 11 组真实数据最慢 0.116s，远低于 OJ 的 1000ms 限制。作为对比，每点跑一次 Dijkstra 的 $O(N \cdot R \log R)$ 在同规模下约 $10^{10}$，不可接受。
• 空间复杂度：双向邻接表 $2R$ 条元组、双标签数组 $2(N+1)$、小根堆 $O(N + R)$，整体 $O(N + R)$。实测峰值 60.9MB（大头是一次性读入的输入字节串），低于 128MB 的内存限制；INF = 10**18 远大于最长简单路 $< 5000 \times 5000 = 2.5 \times 10^7$，哨兵安全。

总结

第二短路问题的难点不是"多跑一遍最短路"，而是单标签 Dijkstra 没有地方安放那些更长但仍可能夺冠的候选。双标签引理证明只需保留每个结点的前两个长度标签即可不重不漏，于是普通 Dijkstra 平凡地推广为"三段式开区间松弛 + 过期项跳过"的双标签版本：复杂度只多一个常数，却把答案直接算了出来。同一框架继续扩展就是 k 短路问题（Yen 算法、Eppstein 算法）的起点。