P3350 [ZJOI2016] Traveler

Xiao Y came to a new city to travel. She found that the city layout is a grid: there are $n$ roads running from east to west and $m$ roads running from south to north. These roads intersect pairwise to form $n \times m$ intersections $(i,j)$, where $1 \le i \le n, 1 \le j \le m$. She found that the conditions of different roads vary, so passing through different intersections takes different amounts of time. After investigation, she learned that going from intersection $(i,j)$ to $(i,j+1)$ takes time $r(i,j)$, and going from $(i,j)$ to $(i+1,j)$ takes time $c(i,j)$. Note that the roads are bidirectional. Xiao Y has $q$ queries and wants to know the minimum time needed to travel from intersection $(x_1,y_1)$ to intersection $(x_2,y_2)$.

The first line contains 2 positive integers $n, m$, representing the size of the city. The next $n$ lines each contain $m-1$ integers. In the $i$-th line, the $j$-th positive integer represents the time $r(i,j)$ to move between adjacent intersections. The next $n-1$ lines each contain $m$ integers. In the $i$-th line, the $j$-th positive integer represents the time $c(i,j)$ to move between adjacent intersections. The next line contains a single positive integer $q$, the number of Xiao Y’s queries. The following $q$ lines each contain 4 positive integers $x_1, y_1, x_2, y_2$, representing the positions of two intersections.

Output $q$ lines. Each line contains a single integer, the minimum time required to travel from one intersection to the other.

Constraints - $n \times m \le 2 \times 10^4$. - $q \le 10^5$. - $1 \le r(i,j), c(i,j) \le 10^4$. Translated by ChatGPT 5