明显可以利用斜率优化加速转移。 但是问题在于路径是一个持续性的过程，即 p i 和 q i 之间可能相距很远。不过我们完全可以将 p i 和 q i 拆成 一次询问 和 一次尾部插入 两个事件，这样事件就可以通过排序变成时间单调递增的了。 接下来考虑 x 和 y ，也就是起点和终点。不过这可以用上面一样的方法处理，也就是将起点和终点拆成两个操作。我们依然维护单调队列，但是因为每个事件对应的地点有区别，因此我们对每个点开一个 vector ，分别维护即可。 记得在 1 号点预先放一个 0 时刻 0 代价的点作为起点。答案可以在路径终点是 n 的时候直接统计，n 号点就没必要再开 vector 了。 时间复杂度瓶颈在排序上。因为数据范围特别小，因此可以直接采用统排。时间复杂度 O(M+T)，其中 T 是时间范围的最大值。 代码