严格次短路：双距离维护与状态松弛

一、认知颠覆：次短路到底是在求什么？

很多同学一听到“次短路”，脑海里立刻冒出两个自以为很妙的“贪心”想法：

想法一：“先跑一遍最短路，把最短路上的某条边删掉，再跑一遍 Dijkstra 不就是次短路了吗？”
想法二：“求出所有路线按长度排序，排在第一名的是最短路，那第二名不就是次短路吗？”

这两个想法在考场上会让你全军覆没。在动手写任何代码之前，必须先厘清两个底层的图论定义：

1. 简单路径 (Simple Path) vs 行走 (Walk)

简单路径 (Simple Path)：每个节点至多只能经过一次，绝对不许走回头路。
行走 (Walk)：允许重复经过节点和边。只要有路，你可以在两条边之间反复横跳、来回折返。

在信奥竞赛（如洛谷 P2865 [USACO06NOV] Roadblocks G）的标准次短路模型中，题目考察的绝大多数是 Walk（允许重复走点和边）。如果允许走回头路，刚才“删掉最短路上的一条边”的做法就彻底崩塌了——因为真正的次短路往往完整包含了最短路的所有边，只是在某条边上多折返了一趟！

2. 严格次短 (Strictly Second Shortest) vs 非严格次短

假设从起点到终点有两条完全不同的路线，但它们的长度都是 $10$ 。它们算“最短”和“次短”吗？

非严格次短：只按路线编号排队，允许长度并列。此时第二条长度为 $10$ 的路线就算次短路。
严格次短：按距离数值去重！距离集合为 $\{10, 14, 18 \dots\}$ 。排在第一的距离是 $10$ ，排在第二的距离必须是严格大于 $10$ 的最小值（即 $14$ ）。两条并列长度为 $10$ 的路线，在严格次短眼中都只能算“最短路”。

本文聚焦最经典、最常考的竞赛标准模型：边权为正、允许重复经过点和边、求严格大于最短距离的第二种距离（严格次短 Walk）。

二、三个具象切片：看透“严格”与“折返”

为了彻底建立直观感觉，我们来看三个极简图：

1. 切片 1：等长菱形图（去重的重要性）

考察由节点 $1, 2, 3, 4$ 组成的对称菱形图：边为 $(1,2), (2,4), (1,3), (3,4)$ ，四条边的权值全部为 $1$ 。

路线 A： $1 \to 2 \to 4$ ，总长度为 $2$ 。
路线 B： $1 \to 3 \to 4$ ，总长度为 $2$ 。

虽然路线 A 和路线 B 经过了完全不同的节点，但它们的长度完全相同，都等于 $2$ 。距离数值没有更新，第二条路线不能算作“第二种距离”。

那严格次短距离是多少？在允许折返的规则下，我们可以走：

1 \to 2 \to 1 \to 2 \to 4

在这条走法中，我们在边

(1, 2)

上来回蹭了一圈，总长度为

1 + 1 + 1 + 1 = 4

。全图没有任何走法的长度等于

3

，因此：最短距离是

2

，严格次短距离是 $4$ 。

四条单位边组成的无向菱形有两条长度2的最短路线，但严格次短walk长度为4，例如1→2→1→2→4。

2. 切片 2：单边图（删边法的致命破绽）

全图只有两个点 $1$ 和 $2$ ，中间连着一条权值为 $5$ 的无向边。

最短距离： $1 \to 2$ ，长度为 $5$ 。
严格次短距离： $1 \to 2 \to 1 \to 2$ ，长度为 $5 + 5 + 5 = 15$ 。

如果你用了“删边法”，把最短路用的唯一一条边删掉，图直接断成孤岛，程序会告诉你终点不可达！但实际上，正因为可以折返，次短距离实实在在就是 $15$ 。

3. 切片 3：平行重边图

节点 $1$ 和 $2$ 之间有两条无向边，边权分别为 $5$ 和 $7$ 。

最短路走第一条边，长度为 $5$ ；次短路走第二条边，长度为 $7$ 。如果两条重边的权值都是 $5$ ，那么次短距离依然只能通过折返得到 $15$ 。边的物理身份不同，不代表产生的几何距离不同。

三、灵魂设计：双层状态维护与反证法

既然普通 Dijkstra 只能维护一个最优解，那我们为每个节点开辟两个席位：

d1[u]：从起点到节点 $u$ 的最短距离（冠军席位）。
d2[u]：从起点到节点 $u$ 的严格次短距离（亚军席位，必须满足 d2[u] > d1[u]）。

1. 为什么只需要保留前两名？第三名、第四名真的不需要存吗？

这是一个经典的考场疑问：“如果到达终点的次短路，是由某个中间节点的‘第三短路’转移过来的呢？”

我们可以用极具说服力的反证法瞬间击碎这个顾虑：

证明：假设存在一条到达终点 $n$ 的次短行走，它在中间经过了节点 $u$ 。设它在到达 $u$ 时的前半段距离为 $D_{pre}$ ，从 $u$ 走到终点 $n$ 的后半段距离为 $D_{suf}$ ，总长度为 $L = D_{pre} + D_{suf}$ 。

如果 $D_{pre}$ 既不是到 $u$ 的最短距离 d1[u]，也不是到 $u$ 的严格次短距离 d2[u]，那说明它至少排在第三位，即：
$D_{pre} > d2[u] > d1[u]$
现在我们保持后半段走法 $D_{suf}$ 完全不变，仅仅把前半段替换为 d1[u] 和 d2[u]。因为模型允许走 Walk（点边可重复），拼接后的两条新路线依然是合法的行走！

这两套新行走的长度分别为：
$L_1 = d1[u] + D_{suf}$

$L_2 = d2[u] + D_{suf}$
显然满足 $L_1 < L_2 < L$ 。这就意味着在 $L$ 之前，已经存在至少两个严格更小的合法总长度 $L_1$ 和 $L_2$ ！因此 $L$ 绝不可能成为终点的第二种距离。

结论：任何排在第三名及以后的中间状态都是“无效杂质”，中间节点严格只需要保留两个最优席位。

四、核心状态转移：腾挪置换法

在优先队列中，我们每次取出当前全局最小的距离记录 (du, u)。当我们沿着出边 $u \to v$ （权值为 $w$ ）进行松弛时，新产生的候选距离为：

nd = du + w

面对节点 $v$ 手里的 d1[v]（冠军）和 d2[v]（亚军），新来的挑战者 $nd$ 会触发以下三种极其严密的物理情况：

1. 情况 1：挑战冠军成功 ( $nd < d1[v]$ )

新距离比当前的最短路还要短！

新距离理所当然夺得冠军席位。
关键细节：被赶下台的原冠军 d1[v] 并没有死，它虽然丢了冠军，但它绝对比原亚军更有资格争夺第二名！
腾挪操作：我们用 swap(nd, d1[v])。这样新距离进入了 d1[v]，而手里的 $nd$ 变成了“退居二线的旧冠军”。随后把新的 d1[v] 入堆，手里的 $nd$ 顺势流向第二步去继续冲击亚军！

2. 情况 2：挑战亚军成功 ( $d1[v] < nd < d2[v]$ )

如果挑战冠军失败（或者拿着刚才退下来的旧冠军），发现它严格大于当前冠军，但又严格小于当前亚军：

说明它完美填补了冠军与亚军之间的空当。
直接更新亚军：d2[v] = nd，并将 (d2[v], v) 压入优先队列。

3. 情况 3：毫无竞争力的淘汰者 ( $nd == d1[v]$ 或 $nd \ge d2[v]$ )

如果 $nd == d1[v]$ ：这只是一条并列的最短路线，不能产生新的更优严格次短路，坚决不入堆。
如果 $nd \ge d2[v]$ ：连第二名都挤不进，直接扔掉。

4. 优雅的腾挪代码实现

把上述物理过程转化为代码，有一种极为精简优雅的写法：

// nd 是沿边推导出的新距离
if (nd < d1[v]) {
    swap(nd, d1[v]);    // 夺取冠军，旧冠军退到 nd 手中
    q.push({d1[v], v}); // 新冠军入堆
}
// 注意：如果上面触发了 swap，这里的 nd 是刚才的旧冠军；否则就是原来的新候选
if (nd > d1[v] && nd < d2[v]) {
    d2[v] = nd;         // 夺取亚军
    q.push({d2[v], v}); // 新亚军入堆
}

手推验证：假设节点 $v$ 当前的两个席位是 $d1 = 10, d2 = 14$ 。此时来了一个 $nd = 7$ ：

$7 < 10$ ，触发第一个 if：swap(nd, d1[v]) 后， $d1[v] = 7$ ，而 $nd$ 变成了 $10$ 。将 $(7, v)$ 入堆。
代码顺流而下进入第二个 if：此时 $nd = 10$ 。检查发现 $10 > 7$ 且 $10 < 14$ ，条件完全成立！
执行 $d2[v] = 10$ ，将 $(10, v)$ 入堆。最终状态从 $(10, 14)$ 丝滑更新为 $(7, 10)$ 。绝无任何信息丢失！

五、慢动作手推：跟着单边图走一遍堆

我们再把切片 2（节点 $1$ 和 $2$ ，无向边权值 $5$ ）放进这套算法里，看看队列和数组是如何一步步演化的：

初始状态：d1[1] = 0，其余全为 $\infty$ 。堆内有：{(0, 1)}。
第一轮出堆：弹出 (0, 1)。
- 沿无向边走到 $2$ ： $nd = 0 + 5 = 5$ 。
- $5 < d1[2]$ （ $\infty$ ），触发更新：d1[2] = 5。堆内推入：{(5, 2)}。
第二轮出堆：弹出 (5, 2)。
- 沿同一条边倒退回 $1$ ： $nd = 5 + 5 = 10$ 。
- 比对节点 $1$ ： $10$ 没能小于 $d1[1]=0$ ，但在第二个 if 中，发现 $10 > d1[1]$ 且 $10 < d2[1]$ （ $\infty$ ）！
- 触发更新：d2[1] = 10。堆内推入：{(10, 1)}。
第三轮出堆：弹出 (10, 1)。
- 沿边再次走向 $2$ ： $nd = 10 + 5 = 15$ 。
- 比对节点 $2$ ： $15 > d1[2]=5$ 且 $15 < d2[2]$ （ $\infty$ ）。
- 触发更新：d2[2] = 15。堆内推入：{(15, 2)}。
后续状态：后续再弹出的记录所能推算出的距离都在 $20$ 以上，均被 $nd \ge d2$ 拦截，堆迅速清空。

终点 $2$ 的最终结果：d1[2] = 5, d2[2] = 15。完全正确！

💡 警钟长鸣：绝对不能用 vis 数组把节点焊死！
在普通 Dijkstra 中，每个点出堆一次就被标记为永久确定，再也不允许访问。但在次短路中，节点不仅要出堆两次（一次为最短，一次为次短），而且正是通过从次短状态再次出发，才衍生出了邻居的次短路！这里的剪枝底线是：只有当出堆的距离已经大于当前节点的亚军 d2[u] 时，才判定为彻底过期跳过（if (du > d2[u]) continue;）。

六、完整程序一：无向正权图的严格次短距离

输入格式：第一行包含两个整数 $n, m$ ，接下来 $m$ 行每行包含三个整数 $u, v, w$ ，表示一条连接 $u$ 和 $v$ 权值为 $w$ 的无向边。
数据范围： $1 \le n \le 100000$ ， $0 \le m \le 200000$ ， $1 \le w \le 10^9$ 。允许重边与自环。
输出格式：输出从 $1$ 到 $n$ 的严格次短距离。若不存在严格次短路，输出 -1。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005,INF=1e18;

struct Edge{int v,w;};
vector<Edge> g[N];
int d1[N],d2[N];
int n,m;

void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		g[i].clear();
		d1[i]=INF;
		d2[i]=INF;
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	
	// 小根堆维护 pair<距离, 节点编号>
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	
	d1[1]=0;
	q.push({0,1});
	
	while(!q.empty()){
		int du=q.top().first,u=q.top().second;
		q.pop();
		
		// 剪枝：如果弹出的距离连该点的亚军都排不上，纯属过期记录
		if(du>d2[u]) continue;
		
		for(auto e:g[u]){
			int v=e.v,w=e.w;
			int nd=du+w;
			
			// 1. 冲击冠军：更新最短路
			if(nd<d1[v]){
				swap(nd,d1[v]); // 旧冠军移交到 nd 中
				q.push({d1[v],v});
			}
			
			// 2. 冲击亚军：严格大于新冠军，且严格小于当前亚军
			if(nd>d1[v] && nd<d2[v]){
				d2[v]=nd;
				q.push({d2[v],v});
			}
		}
	}
	
	cout<<(d2[n]==INF?-1:d2[n])<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

复杂度分析：每个节点只保留两种最优距离，但暂存报价可能多次入堆。上面的 swap 写法还可能把旧冠军重复入堆、重复扩展一次，不影响答案；每条边仍只会被有效扫描常数次。时间复杂度为 $O((N + M) \log(N + M))$ ，空间复杂度为 $O(N + M)$ ，轻松通过十万级数据。

七、进阶拓展：单边半价优惠的最短路

学完次短路后，很多同学容易犯“模式僵化”的毛病，看到题目里带个“第二方案”或者“打折”，就想把 d2 往上套。我们来看一个看似相近、实则需要全新思维工具的经典实战问题。

1. 问题场景

给定一张有向正权图，求从节点 $1$ 到节点 $n$ 的最少总费用。特别地，你拥有一次特权：整条路线中，最多可以选择一条边享受半价优惠（若边权为 $w$ ，优惠后费用为 $\lfloor w / 2 \rfloor$ ）。其余经过的边均支付全价。

2. 为什么不能直接看 `d2[n]`？

次短路求的是“全图原价走法下的第二名”，而这里的目标依然是最小值（第一名），只是游戏规则赋予了一次“修改单边成本”的权力。两者的物理模型完全不同！

3. 核心思维模型：分段拆解与反图 Dijkstra

一条使用了半价优惠的完整路线，必然可以被精准切分成三段：

前半段：从起点 $1$ 原价走到某条优惠边的起点 $u$ 。
中间段：走选定的优惠边 $u \to v$ ，支付半价 $\lfloor w / 2 \rfloor$ 。
后半段：从优惠边的终点 $v$ 原价走到终点 $n$ 。

如果优惠边敲定为 $u \to v$ ，为了让整体总花费最小，前后两段显然必须各自选择原价的最短路径！

Total(u \to v) = \text{dist}(1 \to u) + \lfloor w / 2 \rfloor + \text{dist}(v \to n)

4. 破题关键：如何瞬间拿到所有点到终点的距离？

从 $1$ 跑正图，得到 ds[u]；从 $n$ 跑反图，得到 dt[v]，它正好就是原图中从 $v$ 到 $n$ 的最短距离。反图为什么能这样用，可回看《最短路与状态建图》第九节第 1 小节；这里拿到两端距离后，代入上一小节的拼接式即可。

5. 手算验证：优惠一定要给全图最大的边吗？

看一个直观小例子：

有向边： $1 \to 2$ (权值 $3$ )， $2 \to 3$ (权值 $9$ )， $1 \to 3$ (权值 $10$ )。
若不走打折，原价最短路是直达边 $1 \to 3$ ，费用为 $10$ 。
现在我们枚举每条边作为优惠边：
1. 优惠给 $1 \to 3$ ：费用为 $0 + \lfloor 10/2 \rfloor + 0 = 5$ 。
2. 优惠给 $2 \to 3$ ：费用为 $3 + \lfloor 9/2 \rfloor + 0 = 3 + 4 + 0 = 7$ 。
3. 优惠给 $1 \to 2$ ：费用为 $0 + \lfloor 3/2 \rfloor + 9 = 0 + 1 + 9 = 10$ 。
最优答案是 $5$ 。

注意到，边 $2 \to 3$ 的权值是 $9$ ，虽然比 $3$ 大得多，但把优惠给它只能得到 $7$ ，不如给边权为 $10$ 的直达边。优惠方案的优劣取决于整条路径拼合后的总代价，绝不能孤立地贪心选择单条大边。

八、完整程序二：最多一次单边半价的最短路

输入格式：第一行包含两个整数 $n, m$ ；接下来 $m$ 行每行包含三个整数 $u, v, w$ ，表示一条从 $u$ 到 $v$ 权值为 $w$ 的有向边。
数据范围： $1 \le n \le 100000$ ， $0 \le m \le 200000$ ， $1 \le w \le 10^9$ 。
输出格式：输出最少费用。若无法到达输出 -1。若 $n = 1$ ，输出 0。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005,INF=1e18;

struct Edge{int v,w;};
struct Road{int u,v,w;};

vector<Edge> g[N],rev[N];
vector<Road> roads;
int ds[N],dt[N];
int n,m;

// 通用 Dijkstra 模板：传入起点、邻接表与目标距离数组
void dijkstra(int s,vector<Edge> adj[],int dis[]){
	for(int i=1;i<=n;i++) dis[i]=INF;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	
	dis[s]=0;
	q.push({0,s});
	
	while(!q.empty()){
		int du=q.top().first,u=q.top().second;
		q.pop();
		if(du>dis[u]) continue;
		
		for(auto e:adj[u]){
			int v=e.v,w=e.w;
			if(du+w<dis[v]){
				dis[v]=du+w;
				q.push({dis[v],v});
			}
		}
	}
}

void solve(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		roads.push_back({u,v,w});
		g[u].push_back({v,w});     // 原图
		rev[v].push_back({u,w});   // 反图
	}
	
	// 1. 正向跑一次：求起点 1 到所有点的最短距离
	dijkstra(1,g,ds);
	
	// 2. 反向跑一次：求所有点到终点 n 的最短距离
	dijkstra(n,rev,dt);
	
	// 3. 初始答案：最多使用一次优惠，意味着可以一次都不用（全额原价）
	int ans=ds[n];
	
	// 4. 枚举每一条边作为享受半价的优惠边
	for(auto e:roads){
		int u=e.u,v=e.v,w=e.w;
		// 如果起点到不了 u，或者 v 到不了终点，则该边无法拼成合法路径
		if(ds[u]==INF || dt[v]==INF) continue;
		ans=min(ans,ds[u]+w/2+dt[v]);
	}
	
	cout<<(ans==INF?-1:ans)<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

设计亮点：
1. ans 初始化为 ds[n]，自然涵盖了“一次优惠都不用”的合法边界。
2. 若 $n=1$ ，ds[1] = 0，答案直接为 $0$ ，无需编写特殊的补丁判断。
3. 两次单源最短路加一次边集线性扫描，总时间复杂度严格控制在 $O((N + M) \log N)$ 。

九、次短简单路径与 K 短路的分野（选学）

在继续深入前，我们需要明确本篇维护的“次短 Walk（允许折返）”与另外两个著名图论难题的物理区别，避免在考场上张冠李戴。

次短简单路径 (Second Shortest Simple Path)
- 规则底线：绝对不允许走回头路，任何节点至多经过一次。
- 痛点：因为不能折返，我们双状态松弛的“蹭边”魔法彻底失效了。求简单次短路通常使用 Yen 算法：它涉及枚举最短路上的节点作为候选偏离点，限制前缀并屏蔽已用边，再寻找替代路径。这与我们维护两个数值席位的逻辑完全不同。
K 短路 (K-Shortest Paths)
- 规则底线：求出第 3 短、第 4 短……直到第 $K$ 短的路线（通常允许重复经过点边）。
- 痛点：我们的双层状态机，专门为高效锁定**“严格第二”*而生。两层距离只适用于求严格次短，不能为了求第 $K$ 短就想当然地开 $K$ 层数组。求小 $K$ 游走更正宗的做法是利用 Dijkstra 距离单调递增的性质（允许节点多次弹出出堆），或者建立反图结合 A 启发式搜索。

十、进阶操作：还原严格次短行走的回溯链（选学）

求出次短距离只是第一步，如果题目要求打印这条次短路线的具体走法，我们该如何记录回溯链？

在普通 Dijkstra 中，我们用 pre[v] = u 记录“是从哪个点走过来的”。但在双层席位体系中，如果你只用 pre[v][0] 和 pre[v][1] 这种“可变槽位”来记录前驱，会遭遇一个致命的逻辑崩塌：当旧冠军 d1[v] 被新距离挤占，降级为亚军 d2[v] 时，原本指向它的历史前驱关系可能会被后续更新覆盖或切断。

1. 破局之法：不可变历史节点 (Immutable History Node)

为了保证回溯链绝对可靠，我们放弃修改旧槽位，转而采用类似“版本控制”的思想：每一次成功更新出新的最短或次短距离，我们都为它颁发一个全局唯一的“历史身份证（编号）”，并把当前节点和它爸爸的身份证号永远固化下来。

另外，针对冠军降级，我们不需要手动把旧冠军重新塞回队列。为什么？因为旧冠军在当年诞生时，早就已经被压入优先队列了！我们只需要在代码里执行 d2[v] = d1[v]，这个旧冠军的队列记录在未来出堆时，自然就能通过 du <= d2[v] 的存活校验，继续向外围扩散次短路的波纹。这种“顺势而为”的代码，既无漏洞又极度精简。

因此，下面的程序三在冠军降级时，比程序一少一次旧冠军的重复入堆；两种写法的距离答案相同。

2. 完整程序三：带路径还原的严格次短路

输入格式：第一行 $n, m$ ；接下来 $m$ 行 $u, v, w$ (无向正权图)。 数据范围： $1 \le n \le 100000$ ， $0 \le m \le 200000$ ， $1 \le w \le 10^9$ 。 输出格式：第一行输出严格次短距离（无解输出 -1），第二行输出具体的节点轨迹（空格隔开）。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005, INF = 1e18;

struct Edge { int v, w; };
vector<Edge> g[N];
int d1[N], d2[N];
int n, m;

// 历史节点，用于不可变回溯
struct Node {
	int v;
	int pre_idx; // 走过来的上一步在 history 中的下标
} history[N * 20]; // 空间开大，每次有效入队都分配新节点
int node_cnt = 0;

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		d1[i] = INF;
		d2[i] = INF;
	}
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}

	// pair<距离, 历史节点编号>
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

	d1[1] = 0;
	history[++node_cnt] = {1, 0};
	q.push({0, node_cnt});

	int final_path_idx = 0; // 记录终点次短路对应的历史节点编号

	while (!q.empty()) {
		int du = q.top().first;
		int idx = q.top().second;
		int u = history[idx].v;
		q.pop();

		// 剪枝：如果弹出的距离连该点的亚军都排不上，说明是彻底过期的记录
		if (du > d2[u]) continue;

		// 锁定次短路的终点 idx（因为优先队列按距离升序出队，遇到 d2[n] 必然是真次短）
		if (u == n && du == d2[n] && final_path_idx == 0) {
			final_path_idx = idx;
		}

		for (auto e : g[u]) {
			int v = e.v, w = e.w;
			int nd = du + w;

			// 1. 冲击冠军：更新最短路，同时旧冠军自动降级
			if (nd < d1[v]) {
				d2[v] = d1[v];
				d1[v] = nd;
				history[++node_cnt] = {v, idx};
				q.push({nd, node_cnt});
			}
			// 2. 冲击亚军：严格大于新冠军，且严格小于当前亚军
			else if (nd > d1[v] && nd < d2[v]) {
				d2[v] = nd;
				history[++node_cnt] = {v, idx};
				q.push({nd, node_cnt});
			}
		}
	}

	if (d2[n] == INF) {
		cout << -1 << '\n';
	} else {
		cout << d2[n] << '\n';
		// 沿着历史节点的 pre_idx 顺藤摸瓜即可完美还原路径
		vector<int> path;
		int curr = final_path_idx;
		while (curr != 0) {
			path.push_back(history[curr].v);
			curr = history[curr].pre_idx;
		}
		reverse(path.begin(), path.end());
		for (int i = 0; i < path.size(); i++) {
			cout << path[i] << (i == path.size() - 1 ? "" : " ");
		}
		cout << '\n';
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

【实战测试样例】

输入： 3 3 1 2 5 1 2 5 2 3 100

输出： 115 1 2 1 2 3

(注：起点到节点 2 有两条平行同权边，最短距离是 5，次短距离通过折返产生为 15，最终到达 3 的最短距离是 105，次短距离是 115)

十一、核心自测：同权、折返与不可达的极致边缘

为了检验你是否真正吃透了上述模型，请拿出一张草稿纸，把刚刚代码样例中的一条重边改为 6，再增加一个不可达孤岛。

💡 【自拟边界练习：迷雾小镇】 给定一张无向图，包含 4 个节点：

节点 1 到节点 2 之间，有两条平行的重边，权值分别为 5、6。

节点 2 到节点 3 之间，只有一条边，权值为 100。

节点 4 是一个孤立点，不与任何点相连。

问题：起点为 1，请分别写出到达节点 3 和节点 4 的最短距离 d1 与严格次短距离 d2。

深度解析与答案：

对于节点 3：
- 最短距离 d1[3]： $5 + 100 = 105$ 。
- 坑点预警：别照搬前面同权重边样例的 115！这里走权值为 6 的那条边，就能得到一个新的距离。
- 物理真相：折返仍能得到 115，但它已经排不到第二名了。两条路线的长度分别为 105、106，恰好占据冠军和亚军席位。
- 严格次短距离 d2[3]： $6 + 100 = 106$ 。
对于节点 4：
- 它是绝对不可达的孤岛，没有任何边能波及它。
- 答案：d1[4] = d2[4] = INF（未被更新的极大值初始值）。

如果你能瞬间避开重边的陷阱，说明你已经对“严格去重”和“折返延宕”建立了极其稳固的防线！

十二、避坑自查清单与渐进式题单

在把代码交上评测机之前，花三十秒对照以下三条铁律自查：

无穷大上界是否爆开：次短路的距离往往大于最短路。在边权为 $10^9$ 、边数为 $2 \times 10^5$ 的图上，最长距离可能达到 $2 \times 10^{14}$ 以上。普通 0x3f3f3f3f 会当场暴毙，必须使用 1e18 并全局开启 long long。
vis 标记的滥用：次短路算法绝不能给节点打单次访问标记，出堆剪枝只能依据 du > d2[u]。
严格不等号校验：在维护双层席位时，切记只有当候选距离严格大于冠军（nd > d1[v]）时才能竞选亚军；漏掉这个判断，你的程序就会把等长最短路当成次短路输出。

1. 实战进阶题单

第一阶段：严格次短路肌肉记忆

洛谷 P2865 [USACO06NOV] Roadblocks G
- 训练指引：本讲程序一的原型题。反复手写本篇的“腾挪置换法”，深刻体会为什么无向正权图的次短路一定能通过有限次折返被堆算法捕捉。

第二阶段：反图与分段拆解 2. 洛谷 P1629 邮递员送信（复习）

训练指引：反图最短路的基石题目。去程是单源最短路，回程是多源汇聚到单点。建立反图后，一次 Dijkstra 解决所有回程距离。

第三阶段：状态维度泛化（分层图） 3. 洛谷 P4568 [JLOI2011] 飞行路线（复习）

训练指引：如果题目不是“最多一次半价”，而是“最多免费乘坐 $k$ 次航班”（ $k \le 10$ ），单纯的正反图枚举就不够用了。此时需要将“优惠次数”压入状态，开出 $dist[u][k]$ 的二维分层图状态，在状态转移中完成更高维度的拓展。

严格次短路