Dijkstra 同时维护每点严格不同的最短与次短距离。
OJ: luogu
题目 ID: P2865
难度:普及+/提高-
标签:次短路Dijkstra最短路python
日期: 2026-07-17 03:00
题意
求从 1 到 n 严格长于最短路的最小路径长度，路径允许回退。
思路
每个节点保存 shortest 和 second。新候选若小于最短，就先把旧最短交换出来，再尝试作为次短；只有满足 shortest < candidate < second 才更新次短。
Python 知识
- 多重赋值完成旧最短与候选的交换。
- 一个最小堆同时处理最短和次短状态。
- 严格不等号排除与最短路等长的另一条路径。
代码
python
import sys
from heapq import heappop, heappush
input = sys.stdin.buffer.readline
n, edges = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(edges):
u, v, weight = map(int, input().split())
graph[u].append((v, weight))
graph[v].append((u, weight))
infinity = 10**30
shortest = [infinity] * (n + 1)
second = [infinity] * (n + 1)
shortest[1] = 0
heap = [(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, 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])原有 C++ 版本仍保留：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000 + 5;
const int MAXM = 100000 * 2 + 5;
const long long INF = (1LL << 60);
struct HeapNode {
int u;
long long dist;
bool operator < (const HeapNode &other) const {
return dist > other.dist;
}
};
int n, r;
int head[MAXN], to[MAXM], nxt[MAXM], w[MAXM], edge_cnt;
long long dist1[MAXN], dist2[MAXN];
void init_graph() {
edge_cnt = 0;
for (int i = 1; i <= n; i++) {
head[i] = 0;
}
}
void add_edge(int u, int v, int len) {
edge_cnt++;
to[edge_cnt] = v;
w[edge_cnt] = len;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
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 (int i = head[u]; i != 0; i = nxt[i]) {
int v = to[i];
long long nd = d + w[i];
// 如果找到了更短的最短路，原来的最短路就可能降级成次短路。
if (nd < dist1[v]) {
long long old_shortest = dist1[v];
dist1[v] = nd;
nd = old_shortest;
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;
init_graph();
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)。
总结
次短路不是“第二条被找到的路径”，而是严格大于最短值的最小距离。