[ZJOI2016] 旅行者

网格图有一个优美的性质，它的最小割的大小等于较短边的长度，不超过 $\sqrt S$，其中 $S$ 为网格图面积。

所以网格图上的最短路可以分治地做，网格上一块矩形区域，在较长边中点处切开。此时两个点间的最短路分为，只经过其中一部分的和跨过切面的。只经过其中一部分的，分治处理；跨过切面的，我们以切面上每个点为源，在整个区域内求最短路。对于一块面积为 $S$ 的矩形区域，所需时间为

$$\displaylines{T(S)=2T\left(\frac S2\right)+\sqrt S\cdot S\log S }$$

根据主定理有 $T(S)=O(S^\frac32\log S)$。