一般来讲建凸包是按照 \(k\) 排序插入，实际上问题中如果有 \(x \ge 0\)，按照 \(b\) 排序亦可，有时会起到意想不到的效果。
本题便是一个很好的例子。由于最短路更新过程的特殊性，每次只有 \(b\) 最小的函数会加入凸包中，但由于边权 \(\ge0\)，直接这样建凸包就是正确的。然后使用延迟更新的套路，每次凸包插入边只更新能更新的第一个点，等这个点出队再向后推进即可。
关于凸包
发布时间 2023-12-27 08:37:10作者: Hypercube07
一般来讲建凸包是按照 \(k\) 排序插入，实际上问题中如果有 \(x \ge 0\)，按照 \(b\) 排序亦可，有时会起到意想不到的效果。
本题便是一个很好的例子。由于最短路更新过程的特殊性，每次只有 \(b\) 最小的函数会加入凸包中，但由于边权 \(\ge0\)，直接这样建凸包就是正确的。然后使用延迟更新的套路，每次凸包插入边只更新能更新的第一个点，等这个点出队再向后推进即可。