如何在O(mlogn)时间内找含至多一条危险边的最大最小权路径？

核心技巧：给节点做「状态分身」 #

你可以把每个顶点拆成两个节点：

• u_0：代表走到u的时候，还没用过任何危险边
• u_1：代表走到u的时候，已经用了一条危险边

然后根据原边的类型，给这个新图加边：

• 对非危险边(u, v)，权值w：
  • 加双向边u_0 ↔ v_0，权值w（没碰过危险边的状态下继续走安全边）
  • 加双向边u_1 ↔ v_1，权值w（已经用了危险边，继续走安全边）
• 对危险边(u, v)，权值w：
  • 加双向边u_0 ↔ v_1和v_0 ↔ u_1，权值w（从没用过危险边的状态，通过这条危险边切换到已用状态，而且只能切换一次，所以不用加u_1到v_1的边）

用改进版Dijkstra求最大瓶颈路径 #

接下来就可以用你熟悉的改进版Dijkstra（求最大瓶颈的那种）来处理这个新图：

1. 维护两个数组：dist0[u]是走到u_0时的最大瓶颈值（路径上最小权值的最大值），dist1[u]是走到u_1时的最大瓶颈值。初始时dist0[起点]设为一个极大值，其他都设为0。
2. 用最大堆（优先队列）选择当前瓶颈值最大的节点，每次取出节点后遍历它的邻边：
   • 计算新的瓶颈值：new_val = min(当前节点的dist值, 边的权值)
   • 如果new_val比邻接状态节点的当前dist值大，就更新dist值，并把邻接节点加入堆。
3. 最后取终点的dist0[终点]和dist1[终点]中较大的那个，对应的路径就是满足要求的最优路径。

为什么时间复杂度是O(m log n) #

拆点后总节点数是2n，总边数仍为O(m)级别（非危险边对应4条新边、危险边对应2条新边，整体数量和原边数线性相关）。优先队列每个边最多处理一次，每次堆操作的时间是O(log(2n))=O(log n)，因此整体时间复杂度为O(m log n)，符合要求。

另一种思路：结合最大生成树 #

如果你不想用拆点法，也可以尝试这个方案：

1. 先移除所有危险边，构建最大生成树，算出起点到终点的最大瓶颈值（这是不使用危险边的最优解）。
2. 用倍增法预处理最大生成树中任意两点间路径的最小权值，预处理时间为O(n log n)。
3. 对每条危险边(u, v, w)，计算两种路径的瓶颈值：
   • 起点→u（最大生成树路径）→危险边→v→终点（最大生成树路径）：瓶颈值为min(起点到u的瓶颈, w, v到终点的瓶颈)
   • 起点→v（最大生成树路径）→危险边→u→终点（最大生成树路径）：瓶颈值为min(起点到v的瓶颈, w, u到终点的瓶颈)
4. 把所有危险边计算出的瓶颈值和第一步的无危险边瓶颈值对比，最大的那个就是答案。

内容的提问来源于stack exchange，提问作者Julie Guo