解题思路

网格四联通，边权为相邻格子频点差的绝对值。另可把相同频点的格子视为一次免费跳线（全图限用一次）。把每种频点连到一个虚点，最短路状态带是否已跳线。

复杂度分析

时间复杂度 $O(nm\log(nm))$ ，空间复杂度 $O(nm)$ 。

机房里有 $n$ 行 $m$ 列设备格点，格子 $(i,j)$ 上的端口频点为 $a_{i,j}$ 。运维从左上角走到右下角，每一步可以走到上、下、左、右相邻格子，耗时为两格频点差的绝对值。

此外至多使用一次同频跳线：从某个格子瞬间转移到另一个频点相同的格子，这次转移不耗时。跳线全图限用一次。

请计算从左上角走到右下角的最少耗时。

约束： $1 \le n,m \le 5 \times 10^{2}$ ， $1 \le a_{i,j} \le 1000000000$ 。