P4150 [WC2009] Shortest Path Problem

A $6 \times n$ grid is given, where each cell initially has a non-negative weight. There are two types of operations: - Change the weight of a cell (the new weight is still non-negative). - Query the weight of the shortest path between two cells. Notes and task: For any cell $P$, its coordinates $(x_P, y_P)$ satisfy $1 \leq x_P \leq 6$, $1 \leq y_P \leq n$. The Manhattan distance between cells $P$ and $Q$ is defined as $|x_P - x_Q| + |y_P - y_Q|$. An ordered sequence of cells $(p_1, p_2, \ldots, p_k)$ is called a path from $p_1$ to $p_k$ if the Manhattan distance between any $p_i$ and $p_{i+1}$ is $1$. Its weight is $d(p_1) + d(p_2) + \cdots + d(p_k)$, where $d(P)$ is the weight of cell $P$. The shortest path between two cells $P$ and $Q$ is a path from $P$ to $Q$ with the minimum total weight.

The first line contains an integer $n$. The next $6$ lines each contain $n$ integers; on the $(i+1)$-th line, the $j$-th integer is the initial weight of cell $(i, j)$. Then an integer $Q$ follows, and the next $Q$ lines each describe an operation. There are two types of operations: Type $1$: "1 x y c" (without double quotes). Set the weight of cell $(x, y)$ to $c$ ($1 \leq x \leq 6$, $1 \leq y \leq n$, $0 \leq c \leq 10000$). Type $2$: "2 x_1 y_1 x_2 y_2" (without double quotes). Query the weight of the shortest path between cell $(x_1, y_1)$ and cell $(x_2, y_2)$ ($1 \leq x_1, x_2 \leq 6$, $1 \leq y_1, y_2 \leq n$).

For each type $2$ operation, in the order they appear, output one line with one integer: the weight of the shortest path.

| Testdata ID | $n$ | $Q$ | Testdata ID | $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$ | **2024/08/20: Added 3 sets of hack testdata.** Translated by ChatGPT 5