Luogu3350 [ZJOI2016] 旅行者

题意：给出一个 的网格图，边权非负， 次询问两点间最短路。

，，时限 。

---

平面图分治。

对可能的最短路径进行分治。

一刀将当前矩形区域切成两半，考虑所有跨越分界线的路径的贡献。

首先，给每个分界线上的点求该区域内的单源最短路。这需要使用 。

• 询问点对跨过分界线。

  显然，此时所有可能的最短路都一定跨过分界线。

  枚举路径经过分界线的某一个点（可能穿过多次，但没关系）贡献答案。

• 询问点对未穿过分界线。

  此时最短路可能穿过分界线，也可能没穿过。

  穿过的贡献 ：枚举路径经过分界线的某一个点贡献答案。

  对于没穿过的情况，分治成子问题。

选择分割线时，将当前的长边均匀切分。

---

复杂度分析：

对 的矩形进行分析，下面默认 。

最短路复杂度 ：对一个 的矩形求解，需要做 次 的 ，复杂度为 。

询问复杂度 ： 对一个 的矩形求解，每个询问消耗的复杂度为 。

先将原矩形分拆成 的 个小矩形。

分治树有 层，最短路复杂度为 ，询问复杂度为 。

接下来分析方形的复杂度。

设 为边长为 的方形的最短路复杂度。

有 ，可得复杂度为 。

对于某个询问，其所在区域的最短边不断减半，求和后即为 。

综上，复杂度为 。

若设 ，当 时复杂度最大，为 。

轻微卡常。