P9550 "PHOI-1" Banquet

After traveling a long distance in City Z, Xiao X is going to attend someone else's banquet. 

City Z is an $n \times n$ matrix. Xiao X plans to reach the banquet using only a teleporter and a time-space traveler. If Xiao X is currently at position $(p,q)$ satisfying $l1_x \le p \le r1_x$ and $l2_y \le q \le r2_y$ $(0 \le l1_x \le r1_x < x,0 \le l2_y \le r2_y < y)$, then Xiao X can reach position $(x,y)$. However, because the teleport technology is not very mature and due to the influence of the time-space traveler, each teleport costs $w_p+w_q+w_x+w_y-p-q-x-y$ seconds (because of the nature of the time-space traveler, the time may be negative). If an index is not a positive integer, the teleporter will be damaged, so Xiao X can only reach positions whose indices are all positive integers. Now Xiao X is at $(1,1)$. He wants to attend the banquet, but he does not know where it is. So he wants you to compute the minimum time needed to reach every position $(x,y)$ $(1 \le x,y \le n)$. If a position cannot be reached, output `inf`.

Line $1$ contains an integer $n$, the size of the matrix. Line $2$ contains $n$ non-negative integers: $l1_1,l1_2 \ldots l1_n$. Line $3$ contains $n$ non-negative integers: $r1_1,r1_2 \ldots r1_n$. Line $4$ contains $n$ non-negative integers: $l2_1,l2_2 \ldots l2_n$. Line $5$ contains $n$ non-negative integers: $r2_1,r2_2 \ldots r2_n$. Line $6$ contains $n$ non-negative integers: $w_1,w_2 \ldots w_n$. The testdata guarantees that $l1_i \le r1_i$ and $l2_i \le r2_i$.

Output $n$ lines, each containing $n$ integers. The integer in row $i$ and column $j$ denotes the shortest path length from $(1,1)$ to $(i,j)$.

**This problem uses bundled testcases.** | Subtask | $n$ | $l1_i,l2_i$ | $w_i$ | Score | | :-: | :-: | :-: | :-: | :-: | | $0$ | $1 \le n \le 70$ | No special constraints | $i \le w_i \le 10^5(1 \le i \le n)$ | $15$ | | $1$ | $1 \le n \le 70$ | No special constraints | No special constraints | $25$ | | $2$ | No special constraints | $l1_i=l2_i=r1_i=r2_i=1(2 \le i \le n)$ | No special constraints | $5$ | | $3$ | No special constraints | No special constraints | No special constraints | $55$ | For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^3$, $0 \le l1_i \le r1_i \le n$, $0 \le l2_i \le r2_i \le n$, $0 \le w_i \le 10^5$, and $l1_i \le r1_i < i$, $l2_i \le r2_i < i$. ### Sample Explanation #1: - From $(1,1)$ to $(1,1)$ obviously takes $0$ seconds. - From $(1,1)$ you can directly reach $(2,2)$, costing $w_1 + w_1 + w_2 + w_2 - 1 - 1 - 2 - 2 = -2$ seconds. - From $(1,1)$ you can also directly reach $(3,2)$, costing $w_1 + w_1 + w_3 + w_2 - 1 - 1 - 3 - 2 = 1$ seconds. - To reach $(3,3)$ from $(1,1)$, you need to go from $(1,1)$ to $(2,2)$ first, then from $(2,2)$ to $(3,3)$. The cost is $w_1 + w_1 + w_2 + w_2 - 1 - 1 - 2 - 2 + w_2 + w_2 + w_3 + w_3 - 2 - 2 - 3 - 3 = -4$ seconds. - By manual calculation, you can find that from $(1,1)$ you cannot reach any other position. Translated by ChatGPT 5