Dijkstra 同时维护每点严格不同的最短与次短距离。
OJ: luogu
题目 ID: P2865
难度:普及+/提高-
标签:次短路Dijkstra最短路python
创建: 2026-07-17 03:00
更新: 2026-10-20 19:50
题意
求从 1 到 n 严格长于最短路的最小路径长度，路径允许回退。
思路
先破除一个直觉
“用 Dijkstra 往外走，到达 n 的第一条路径是最短路，第二条就是次短路”——这个想法是错的。
题面明确说次短路可以和最短路共用道路、可以回头。所以对链 1-2-3（边权皆 1），最短路是 2，次短路是 1-2-1-2-3 = 4，它比最短路长，而且走了一遍回头路。
这说明次短路可能不是简单路径，不能在简单路径空间里枚举。“第二条到达”和“长度第二小”是两件事。
状态扩成两个
对每个点维护两个严格不同的距离：
| 变量 | 含义 |
|---|---|
dist1[v] |
到 v 的最小距离 |
dist2[v] |
到 v 的严格大于 dist1[v] 的最小距离 |
用堆按长度升序弹出候选，每条候选都是一条真实路径。松弛 u → v 得到候选 nd 时分两种情形。
情形一：nd < dist1[v]——旧最短路要降级，不能丢。
这是本题唯一一个不写就会错的细节。dist1[v] 的旧值确实是一条到 v 的真实路径，只是不再是最短的。它现在是次短的有力候选，所以不能丢弃：
candidate, shortest[neighbor] = shortest[neighbor], candidate交换之后 candidate 自动变成旧的最短路，直接进入第二个判断去竞争次短。
实测后果：对 1-2 权 4、1-3 权 8、2-3 权 2，不降级的版本会输出 10，而正确答案是 8（1-3 直达）。
情形二：dist1[v] < nd < dist2[v]——直接更新次短。
两个不等号都不能改：
- 严格大于
dist1[v]：长度等于最短路的另一条路径不算次短路。对“两条长度 2 的最短路 + 一条长度 10 直连”的菱形图，改成>=会输出 2（错误），正确是 10 之外的某个值。 - 严格小于
dist2[v]：一旦有更好的次短候选，旧的就可以永久丢弃，这与 Dijkstra 的定型逻辑一致。
这里为什么不需要 visited
main.cpp 里没有 visited[] 数组，却依然正确——因为状态扩成两个后，一个点要合法地被处理两次（一次作为最短路候选，一次作为次短路候选），不能简单地“处理过就跳过”。
定型判断没有消失，而是从“按点”变成“按记录”：
if current > second[node]:
continue这条记录既不是最短也非次短，早已被更优的值取代，展开它不会产生更优答案。于是堆里每条记录最多被有效展开一次——和 visited 达到的效果一样。
也就是说，Dijkstra 依赖的从来不是那个布尔数组，而是“堆弹出的当前最小值不会再被改进”这条单调性；visited 只是它的一个廉价实现。状态扩展后，只需把定型的粒度从“点”换成“记录”。
Python 知识
candidate, shortest[neighbor] = shortest[neighbor], candidate用多重赋值一次完成交换，等价于 C++ 里先存old_shortest再交换。- 一个最小堆同时处理最短路和次短路两种记录，靠
current > second[node]筛掉过期项。 shortest[neighbor] < candidate < second[neighbor]链式比较，语义与两个and完全一致但更易读。- 整数无穷大
10**30，Pythonint任意精度，不必像 C++ 那样担心INF + w溢出。
代码
#!/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-07-17 01:40
# update_at: 2026-10-20 17:50
#
# main.py：次短路。求 1 到 n 严格大于最短路的路径长度中的最小值。
# 题面允许路径共用道路、允许回头，所以次短路可能不是简单路径，
# 例如链 1-2-3（边权皆 1）的次短路是 1-2-1-2-3 = 4。
# 因此把每个点的状态从一个距离扩成两个严格不同的距离：
# shortest[v] 到 v 的最小值；second[v] 严格大于 shortest[v] 的最小值。
# 用堆按长度升序弹出候选，每条候选都是一条真实路径。
# 一个点的最短路被推翻时，旧值不能丢——它仍是真实路径，应降级为次短候选，
# 这就是下面那个多重赋值交换的意义，去掉它结果会错。
# 这里不需要 visited：状态扩成两个后一个点要被处理两次，定型判断从"按点"
# 变成"按记录"，用 current > second[node] 筛掉过期记录即可。
import sys
from heapq import heappop, heappush
INF = 10**30 # 整数哨兵，比任何合法路径都大；Python int 任意精度，不会溢出
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, r = next(data), next(data)
graph: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
for _ in range(r):
u, v, weight = next(data), next(data), next(data)
graph[u].append((v, weight))
graph[v].append((u, weight)) # 道路双向
shortest = [INF] * (n + 1) # 到 i 的最短距离
second = [INF] * (n + 1) # 到 i 的次短距离，要求严格大于 shortest[i]
shortest[1] = 0
heap: list[tuple[int, int]] = [(0, 1)] # (距离, 点编号)，距离在前才能按它比大小
while heap:
current, node = heappop(heap)
# 这条记录既不是最短路也不是次短路，已被更优的值取代，展开它无益
if current > second[node]:
continue
for neighbor, weight in graph[node]:
candidate = current + weight
if candidate < shortest[neighbor]:
# 找到更短的最短路：旧值是真实路径不能丢，
# 交换后 candidate 变成旧的最短路，正好进入下面去竞争次短
candidate, shortest[neighbor] = shortest[neighbor], candidate
heappush(heap, (shortest[neighbor], neighbor))
# 只接受严格大于最短路、且能改善次短的候选；
# 长度等于最短路的另一条路径不算次短路，所以这里是 < 而非 <=
if shortest[neighbor] < candidate < second[neighbor]:
second[neighbor] = candidate
heappush(heap, (candidate, neighbor))
print(second[n])
if __name__ == "__main__":
solve()原有 C++ 版本仍保留：
/**
* 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-07-17 01:40
* update_at: 2026-10-20 20:05
*/
// 次短路：求 1 到 n 严格大于最短路的路径长度中的最小值。
// 题面允许路径共用道路、允许回头，所以次短路可能不是简单路径，
// 例如链 1-2-3（边权皆 1）的次短路是 1-2-1-2-3 = 4，比最短路长且走了一遍回头路。
// 因此不能在简单路径空间里枚举，而是把每个点的状态从一个距离扩成两个严格不同的距离：
// dist1[v] 到 v 的最小值；dist2[v] 严格大于 dist1[v] 的最小值。
// 用堆按长度升序弹出候选，每条候选都是一条真实路径；一个点的最短路被推翻时，
// 旧值不能丢——它仍是真实路径，应降级为次短候选，这正是不写出那个交换就会错的地方。
// 这里不需要 visited 数组：状态扩成两个后一个点要被处理两次，定型判断从"按点"
// 变成"按记录"，用 d > dist2[u] 筛掉过期记录即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000 + 5; // 点数上界 N <= 5000
const long long INF = (1LL << 60);
struct Edge {
int to; // 边指向的点
int w; // 边的长度
};
struct HeapNode {
int u;
long long dist;
// 小根堆：距离大的排后面
bool operator<(const HeapNode &other) const {
return dist > other.dist;
}
};
int n, r;
vector<Edge> g[MAXN]; // g[u]：从 u 出发的全部边
long long dist1[MAXN]; // 到 i 的最短距离
long long dist2[MAXN]; // 到 i 的次短距离，要求严格大于 dist1[i]
void add_edge(int u, int v, int len) {
g[u].push_back({v, len});
}
void dijkstra() {
for (int i = 1; i <= n; i++) {
dist1[i] = INF;
dist2[i] = INF;
}
priority_queue<HeapNode> pq;
dist1[1] = 0;
pq.push({1, 0});
while (!pq.empty()) {
HeapNode cur = pq.top();
pq.pop();
int u = cur.u;
long long d = cur.dist;
// 这条记录既不是最短路也不是次短路，早已被更优的值取代，展开它无益
if (d > dist2[u]) continue;
for (const Edge &e : g[u]) {
int v = e.to;
long long nd = d + e.w;
// 找到了更短的最短路：旧的最短路是真实路径，不能丢，
// 通过交换把它降级成次短候选（交换后 nd 就是旧的最短路值）
if (nd < dist1[v]) {
std::swap(nd, dist1[v]);
pq.push({v, dist1[v]});
}
// 只接受严格大于最短路、且能改善次短的候选。
// 长度等于最短路的另一条路径不算次短路，所以这里是 < 而不是 <=
if (dist1[v] < nd && nd < dist2[v]) {
dist2[v] = nd;
pq.push({v, dist2[v]});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> r;
for (int i = 1; i <= r; i++) {
int u, v, len;
cin >> u >> v >> len;
add_edge(u, v, len);
add_edge(v, u, len); // 道路双向
}
dijkstra();
cout << dist2[n] << '\n';
return 0;
}复杂度
时间 O((n+m) log n)，空间 O(n+m)。每个点最多被有效处理两次，不影响阶。
前提是边权非负：整套做法靠“堆弹出的当前最小值已定型”这条单调性，边权为负时立即失效。
总结
次短路不是“第二条被找到的路径”，而是严格大于最短值的最小距离。它可能不是简单路径，所以要把每个点的状态从一个距离扩成两个。
关键有三点：旧最短路被推翻时要降级为次短候选而不是丢弃；两个不等号都必须是严格的；定型判断从“按点”变成“按记录”，于是不写 visited 也对。