问题概述

给定一个 $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$

算法思路

核心思想：分治 + 最短路

由于网格规模 $n \times m \leq 20000$ 但查询次数 $q$ 很大，不能对每个查询单独跑最短路。

分治策略：

对当前矩形区域 $[x_1, x_2] \times [y_1, y_2]$，选择较长边进行切割

对切割线上的每个点作为源点，跑一次 Dijkstra 最短路算法

对于跨越切割线的查询，最短路必然经过切割线上某点 $p$，距离为：

dist(s,t)=dist(s,p)+dist(p,t) 递归处理不跨切割线的查询

关键实现细节

1. 坐标映射

将二维坐标 $(i,j)$ 映射为一维编号：id=(i−1)×m+j

2. 图构建

每个节点与上下左右四个邻居相连（边界除外）

边权分别为对应的 $r(i,j)$ 或 $c(i,j)$ 值

3. 分治过程

如果区域宽度大于高度，按行切割；否则按列切割

切割线长度不超过 $\sqrt{n \times m} \approx 141$

对切割线上每个点跑 Dijkstra，更新跨切割线查询的答案

4. 查询处理

对于查询 $(sx,sy)$ 到 $(tx,ty)$：

如果两点在同一子区域，递归处理

如果跨越切割线，用切割线上所有点更新答案：

复杂度分析 Dijkstra 次数：每个点参与 $O(\log(nm))$ 次

每次 Dijkstra：$O(\text{区域大小} \times \log(\text{区域大小}))$

总复杂度：约 $O((nm)^{1.5} \log(nm))$

在 $nm \leq 20000$ 时可行