A21614.最短路问题

【问题描述】

一个 $6 * n$ 的方格，初始每个格子有一个非负权值。有如下两种操作形式：

○改变一个格子的权值（改变以后仍然非负）；

○求两个格子之间的最短路的权值。

【注解与任务】

任意格子 $P$ 的坐标$(x_P, y_P)$满足 $1 \leq x_P \leq 6$， $1 \leq y_P \leq n$。格子 $P$ 和 $Q$ 的曼哈顿距离定义为$|x_P - x_Q| + |y_P - y_Q|$。一个有序方格序列$(p_1, p_2, ..., p_n)$，若满足任意 $p_i$ 和 $p_i + 1$ 的曼哈顿距离为 $1$，则称该序列为一条从 $p_1$ 到 $p_n$ 的路径，其权值为$d(p1) + d(p2) + $...$ + d(p_n)$，其中 $d(P)$ 表示格子 $P$ 的权值。两个格子 $P$ 和 $Q$ 之间的最短路定义为从 $P$ 到 $Q$ 权值最小的路径。

第一行一个整数 $n$。接下来 $6$ 行，每行 $n$ 个整数，第 $i + 1$ 行第 $j$ 个整数表示初始格子$(i, j)$的权值。接下来是一个整数 $Q$， 后面的 $Q$ 行，每行描述一个操作。

输入的操作有以下两种形式：

操作 $1$： "$1\ x\ y\ c$"(不含双引号)。表示将格子$(x, y)$的权值改成 $c$ ($1 \leq x \leq 6$, $1 \leq y \leq n$, $0 \leq c \leq 10000$) 。

操作 $2$： "$2\ x_1\ y_1\ x_2\ y_2$"(不含双引号)。表示询问格子$(x_1, y_1)$和格子$(x_2, y_2)$之间的最短路的权值。（$1 \leq x_1, x_2 \leq 6$, $1 \leq y_1, y_2 \leq n$）

对于每个操作 $2$，按照它在输入中出现的顺序，依次输出一行一个整数表示

求得的最短路权值。

数据编号	$n$	$Q$	数据编号	$n$	$Q$
$1$	$10$	$20$	$6$	$10^4$	$3\times 10^4$
$2$	$100$	$200$	$7$	$3.5\times 10^4$	$3\times 10^4$
$3$	$10^3$	$2\times 10^3$	$8$	$5\times 10^4$	$5\times 10^4$
$4$	$10^4$	$10^4$	$9$	$10^5$	$6\times 10^4$
$5$	$10^4$	$10^4$	$10$	$10^5$	$10^5$