问题分析

我们面对一个特殊的二维平面路径搜索问题：

1. 建筑是垂直线段：从 $(x[i], 0)$ 到 $(x[i], h[i])$
2. 天桥是水平线段：从 $(x[l[j]], y[j])$ 到 $(x[r[j]], y[j])$
3. 行人只能沿着建筑和天桥行走，不能在地面（y=0）行走
4. 可以在交点处切换行走方向
5. 目标：从建筑 $s$ 的底部 $(x[s], 0)$ 到建筑 $g$ 的底部 $(x[g], 0)$ 的最短路径长度

关键观察

1. 图的构建

这个问题可以抽象为一个图的最短路径问题：

• 节点：所有重要的交点，包括：
  • 建筑底部点 $(x[i], 0)$（起点和终点所在）
  • 建筑顶部点 $(x[i], h[i])$
  • 天桥与建筑的交点 $(x[i], y[j])$（当天桥经过建筑 $i$ 时）
  • 天桥与天桥的交点（当它们共享端点时）
• 边：沿建筑或天桥行走的线段
  • 边权 = 线段长度（曼哈顿距离，因为路径是正交的）

2. 交点的性质

• 天桥 $j$ 在高度 $y[j]$ 处与所有 $l[j] \le i \le r[j]$ 的建筑相交
• 由于 $x$ 坐标严格递增，天桥是水平的，建筑是垂直的，交点计算很简单：
  • 建筑 $i$ 与天桥 $j$ 有交点当且仅当 $l[j] \le i \le r[j]$ 且 $y[j] \le h[i]$
  • 交点坐标为 $(x[i], y[j])$

3. 图的规模控制

直接枚举所有交点会得到 $O(nm)$ 的节点数，对于 $n,m \le 10^5$ 不可行。需要优化：

• 对于每栋建筑 $i$，只考虑它实际相交的天桥
• 对于每座天桥 $j$，它相交的建筑是一个连续区间 $[l[j], r[j]]$

算法思路

方法一：离散化 + Dijkstra（较直观）

步骤：

1. 离散化所有高度

   • 收集所有 $h[i]$、所有 $y[j]$ 和 0
   • 排序去重，得到高度层级

2. 构建分层图

   • 每层对应一个高度
   • 每栋建筑在它涉及的高度处都有节点
   • 天桥作为水平连接同一高度的节点

3. 添加边

   • 垂直边：同一建筑在不同高度节点间，边权 = 高度差
   • 水平边：同一高度上，相邻建筑通过天桥连接，边权 = $x$ 坐标差

4. 运行最短路算法

   • 从 $(x[s], 0)$ 到 $(x[g], 0)$ 的最短路径
   • 使用 Dijkstra 算法

复杂度分析：

• 节点数：$O(n + m)$ 级别（每栋建筑在相关高度有节点）
• 边数：$O(n + m)$ 级别
• 时间复杂度：$O((n+m)\log(n+m))$

方法二：事件扫描 + 最短路径（更高效）

核心思想：

将问题转化为一维区间覆盖问题：

1. 预处理每栋建筑的"可达天桥"

   • 对于建筑 $i$，找到所有 $y[j] \le h[i]$ 且 $l[j] \le i \le r[j]$ 的天桥
   • 这可以通过对天桥按 $y$ 排序，使用数据结构维护当前活跃的天桥

2. 构建邻接关系

   • 垂直移动：在建筑 $i$ 上，可以从高度 $y_1$ 走到 $y_2$，代价 $|y_1 - y_2|$
   • 水平移动：在同一高度 $y$，如果多栋建筑都被同一天桥覆盖，它们之间可以水平移动

3. Dijkstra 优化

   • 使用优先队列维护当前最小距离
   • 同时更新垂直和水平移动

3. 特殊情况的处理

情况1：无路径

• 如果建筑 $s$ 和 $g$ 没有被任何天桥网络连通
• 输出 -1

情况2：直接路径

• 如果存在天桥同时覆盖 $s$ 和 $g$，且高度足够低
• 路径 = $|x[s] - x[g]| + y + y$（上下天桥）

实现细节

数据结构选择

1. 存储建筑信息：数组存储 $x[i]$, $h[i]$
2. 存储天桥信息：按 $y$ 排序，便于处理
3. 邻接表：对于每个建筑，存储它所在的天桥及对应高度
4. 并查集：可选，用于快速判断连通性

算法优化

1. 懒惰更新：在 Dijkstra 中，不立即生成所有边，需要时再计算
2. 区间查询：使用线段树或平衡树快速找到建筑 $i$ 在高度 $y$ 可以到达哪些天桥
3. 双向搜索：从起点和终点同时进行 Dijkstra

样例分析

样例1

建筑：       天桥：
0: (0,8)     0: 0-1, y=1
1: (3,7)     1: 0-2, y=6
2: (5,9)     2: 0-6, y=8
3: (7,7)     3: 2-3, y=1
4: (10,6)    4: 2-6, y=7
5: (12,6)    5: 3-4, y=2
6: (14,9)    6: 4-6, y=5
起点：1，终点：5

最短路径：

1. 从建筑1底部(3,0)上升到天桥0的(3,1)：代价1
2. 沿天桥0到建筑0的(0,1)：代价3
3. 从(0,1)上升到天桥2的(0,8)：代价7
4. 沿天桥2到建筑6的(14,8)：代价14
5. 从(14,8)下降到建筑5底部？不行！ 实际路径需要更多转换，最终长度27。

复杂度总结

• 时间复杂度：$O((n+m)\log(n+m))$
• 空间复杂度：$O(n+m)$
• 关键难点：高效处理建筑与天桥的交点关系，避免 $O(nm)$ 的显式建图

扩展思考

1. 如果允许在地面行走，问题会简化为简单的 Manhattan 距离
2. 如果天桥可以倾斜，问题变为更复杂的计算几何问题
3. 实时查询多个 $(s,g)$ 对，可以预处理全源最短路径或使用更高级的数据结构

这个问题的核心是将几何约束转化为图论问题，并利用数据的特殊结构（建筑垂直、天桥水平、x坐标有序）进行高效处理。