二维网格(0,0)到(N,N)最小代价路径求解优化咨询

云原生阿岚

2026-5-6

优化方案：二维偏序离线处理 + 线段树

你的问题核心在于网格规模极大（$10^9 \times 10^{9$），无法遍历每个点，只能聚焦**关键节点**：起点、终点、所有快捷方式的起点和终点。之前的方案3思路方向正确，但$O(P}2)$的时间复杂度无法处理$10^5$量级的快捷方式，我们可以通过二维偏序优化将时间复杂度降到$O(P \log P)$，完全满足2秒的时间限制。

核心思路分析

对于任意关键节点$u(x,y)$，从起点到$u$的最短路径$\text{dist}[u]$有三种来源：

直接从起点走普通路径：$\text{dist}[u] = x + y$（曼哈顿距离，因为只能向右或向上移动）。
通过某个节点$v$走普通路径到$u$：$\text{dist}[u] = \min(\text{dist}[u], \text{dist}[v] + (x - v.x) + (y - v.y))$，其中$v.x \leq u.x$且$v.y \leq u.y$（保证能从$v$走到$u$）。
通过快捷方式直接跳转到$u$：$\text{dist}[u] = \min(\text{dist}[u], \text{dist}[A])$，其中$A \to u$是快捷方式（跳转代价为0）。

将第二种情况的式子变形：
$$\text{dist}[v] + (x - v.x) + (y - v.y) = (\text{dist}[v] - v.x - v.y) + (x + y)$$
由于$x + y$是固定值，我们只需要找到所有满足$v.x \leq u.x$且$v.y \leq u.y$的节点$v$中，$\text{dist}[v] - v.x - v.y$的最小值，就能快速计算出第二种情况的最优值。

具体实现步骤

1. 收集并预处理关键节点

收集所有关键节点：起点$(0,0)$、终点$(N,N)$、所有快捷方式的起点$A_i(x1,y1)$和终点$B_i(x2,y2)$。
对节点去重（避免重复处理同一个点）。
为每个节点$u$初始化$\text{dist}[u] = x + y$（普通路径的代价）。
按终点分组存储快捷方式：创建字典pre_shortcuts，其中pre_shortcuts[u]包含所有能跳转到$u$的起点$A$。

2. 离散化y坐标

由于$y$的范围可达$10^9$，无法直接用线段树维护，我们需要对所有节点的$y$坐标进行离散化：

收集所有节点的$y$值，排序并去重，得到一个映射表，将每个$y$值映射到$1 \sim M$的整数（$M$最多为$2 \times 10^5 + 2$）。

3. 离线处理节点（按x坐标排序）

将所有节点按$x$坐标从小到大排序（$x$相同时按$y$从小到大排序），这样处理节点时，所有$v.x \leq u.x$的节点都已被处理过。

4. 用线段树维护二维范围最小值

初始化线段树，所有位置的值为无穷大：

首先处理起点$(0,0)$：计算$\text{val} = \text{dist}[S] - S.x - S.y = 0$，更新线段树中$y=0$对应的位置为$0$。
按排序后的顺序处理每个节点$u$：
1. 查询普通路径的最优前驱：在线段树中查询$y \leq u.y$的最小值$\text{min_val}$，用$\text{min_val} + u.x + u.y$更新$\text{dist}[u]$。
2. 处理快捷方式：遍历pre_shortcuts[u]中的所有起点$A$，用$\text{dist}[A]$更新$\text{dist}[u]$。
3. 更新线段树：计算$\text{val}_u = \text{dist}[u] - u.x - u.y$，将线段树中$u.y$对应的位置更新为当前值与$\text{val}_u$的最小值。

5. 最终结果

处理完终点$(N,N)$后，$\text{dist}[T]$就是从$(0,0)$到$(N,N)$的最短路径长度。

时间复杂度分析

节点去重、排序、离散化：$O(P \log P)$。
每个节点的线段树查询和更新：$O(\log P)$，共$O(P \log P)$。
处理快捷方式：$O(P)$（每个快捷方式被处理一次）。
总时间复杂度为$O(P \log P)$，完全可以在2秒内处理$10^5$量级的快捷方式。

验证示例

用你给出的示例测试：

关键节点：$(0,0)$、$(0,1)$、$(0,2)$、$(1,2)$、$(2,3)$、$(3,3)$。
处理后$\text{dist}[3,3] = 3$，与示例结果一致。

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