这道题的核心在于利用最短路的性质，通过巧妙的更新和堆维护，避免对每次断边都重新跑最短路。

下面用一个表格来梳理解决该题的关键思路：

🛠️ 实现步骤详解

以下是基于上述思路的实现步骤，主要参考：

1. 预处理：

   • 读取输入：存储图结构，并记录交通部指定的最短路径 rode[] 及其边。
   • 编号与标记：对最短路径依次经过的点进行顺序编号（num[]），并标记最短路径上的边（viss[]）。
   • 计算后缀和：从终点 N 开始，逆着最短路径 计算每个编号的点到终点 N 的距离 disn[]。例如 disn[i] = disn[i+1] + edge[rode[i]].w。

2. 初始化：

   • 初始化一个最小堆，用于存储绕行方案。每个方案是一个 (返回点的编号, 该方案的总距离) 的二元组，按总距离排序。
   • 初始化到起点的最短路数组 dis1[]，例如 dis1[1] = 0。

3. 处理每条断边： 按最短路径顺序，依次枚举要删除的边 rode[i]：

   • 清理堆：弹出堆顶所有返回点编号 ≤ 当前断边编号 i 的方案，因为它们没有成功绕过当前断边。
   • 输出答案：如果堆为空，输出 -1；否则，堆顶元素的距离就是当前答案。
   • 更新最短路：将当前断边 rode[i] 的权值累加到其起点的 dis1 值上，得到其终点的 dis1 值。此操作模拟了在原始最短路上前进。
   • SPFA探索绕行：从当前断边的终点 edge[rode[i]].v 开始进行 SPFA：
     • 在松弛过程中，禁止使用最短路径上的边（通过 viss[] 标记判断）。
     • 如果松弛到一个不在最短路径上的点，则正常加入队列。
     • 如果松弛到一个在最短路径上的点（即 num[v] > 0），则意味着找到了一条绕行路径，它从断边后某点离开，最终又回到了最短路径上的点 v。此时，将 (num[v], dis1[v] + disn[num[v]]) 加入堆。这里 dis1[v] 是绕行到达 v 的距离，disn[num[v]] 是 v 沿最短路径到终点的距离，相加即为此绕行方案总长。

💡 复杂度与提示

• 时间复杂度：约为 $O(L \times (SPFA平均扩展 + \log{(可能方案数)}))$。由于SPFA的效率和图的结构有关，且堆操作本身较快，此方法在随机数据下表现尚可，但可能被特殊数据卡超时。
• 实现注意：
  • SPFA时，只对 dis1 数组进行初始化，disn 数组是预处理好的固定值。
  • 堆中存储的是返回点在最短路径上的编号，而非节点编号，便于判断方案是否有效。
  • 谨慎处理边的编号与图中节点关系的映射。

💎 总结

这道题的关键在于转换视角：不从"删除"入手，而是关注新增的绕行路径，并利用堆动态维护有效解。