题解

思路

把“到达某个梯子下端后的最小损失”作为状态。由于梯子只向更高楼层移动，楼层天然构成拓扑序。

做法

子任务 1 可显式维护当前楼层的全部 $m$ 个房间。从左向右、从右向左各扫描一次即可完成同层最短路，再沿梯子更新高层房间，复杂度 $O(nm+k)$。

子任务 2 只保存梯子端点。处理一层时，对每个梯子上端枚举该层所有可达的梯子下端，直接计算 $d+|p-q|x_i-h$，复杂度最坏为 $O(k^2)$。

满分做法仍按楼层处理。把本层所有可达位置与所有待查询的梯子入口按房间号排序。一次从左向右扫描维护 $d-px_i$ 的最小值，得到从左侧到达的代价；再从右向左维护 $d+px_i$ 的最小值，得到从右侧到达的代价。入口的最小值减去梯子收益后更新其终点。顶层房间 $m$ 作为额外查询点即可得到答案。

复杂度

每个梯子端点只参与常数次扫描，总复杂度 $O((n+k)\log k)$，空间复杂度 $O(n+k)$。所有代价必须使用 64 位整数。