[WC2009] 最短路问题

【问题描述】 一个 $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$，按照它在输入中出现的顺序，依次输出一行一个整数表示 求得的最短路权值。

5
0 0 1 0 0
0 1 0 1 0
0 2 0 1 0
0 1 1 1 0
0 0 0 0 0
1 1 1 1 1
5
2 1 2 1 4
1 1 1 10000
2 1 2 1 4
1 2 3 10000
2 1 2 3 3

0
1
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$|