题目描述

给定一个 $n \times m$ 的网格城市，每个路口 $(i,j)$ 到相邻路口有对应的通行时间：

从 $(i,j)$ 到 $(i,j+1)$ 需要时间 $r(i,j)$

从 $(i,j)$ 到 $(i+1,j)$ 需要时间 $c(i,j)$

所有道路都是双向的。现在有 $q$ 个查询，每个查询要求计算从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的最短时间。

数据范围：

$n \times m \leq 2 \times 10^4$

$q \leq 10^5$

$1 \leq r(i,j), c(i,j) \leq 10^4$

解题思路

核心思想：分治 + Dijkstra

本题采用了平面图分治的策略来解决多源多汇最短路径问题：

问题分析：

直接对每个查询运行 Dijkstra 算法的时间复杂度为 $O(q \cdot nm \log(nm))$，在给定数据范围下不可行。

分治思想：

将网格平面递归地划分为更小的区域。在每一层分治中：

选择当前区域的一条"分割线"（行或列）

对分割线上的每个点作为源点运行 Dijkstra

用这些最短路径信息更新所有经过该分割线的查询

关键观察：

任意两点间的最短路径必定经过分割线上的某个点。因此，对于查询 $(x_1,y_1) \to (x_2,y_2)$，其最短路径可以分解为：

dist(S,T)= P∈split-linemin [dist(S,P)+dist(P,T)]

算法流程

初始化：

读入网格数据和所有查询

递归分治：

如果当前区域大小为 $1 \times 1$，直接返回

否则选择较长的维度进行分割：

如果行数 $\geq$ 列数，选择中间行作为分割线

否则选择中间列作为分割线

处理分割线：

对分割线上的每个点运行 Dijkstra，更新所有相关查询

递归子问题：

根据查询点相对于分割线的位置，将查询划分到左右/上下子区域

复杂度分析

时间复杂度

设 $N = n \times m$，$Q = q$：

分治深度：

$O(\log N)$

每层工作量：

分割线上的点数 × Dijkstra 复杂度

分割线长度最多为 $O(\sqrt{N})$

每个 Dijkstra 在 $O(N)$ 个节点上运行，复杂度为 $O(N \log N)$

总复杂度：

$O(N^{1.5} \log^{2} N + Q \log N)$

在数据范围 $N \leq 2 \times 10^4$，$Q \leq 10^5$ 时可行。

空间复杂度

存储网格：$O(N)$

距离数组：$O(N)$

查询存储：$O(Q)$

总空间：$O(N + Q)$