Shortest path on grid - MarisaOJ: Marisa Online Judge

Shortest path on grid

Time limit: 3000 ms
Memory limit: 512 MB
Given an $n \times m$ grid, where each adjacent pair of cells is connected bidirectionally, the weights of the horizontal edges are denoted as $A_{i,j}$, and the weights of the vertical edges are denoted as $B_{i,j}$. For $q$ queries of the form $(a, b, c, d)$, you need to find the shortest path from $(a, b)$ to $(c, d)$. ### Input - The first line contains two integers $n$ and $m$. - The next $n$ lines each contain $m-1$ integers representing $A_{i,j}$. - The next $n-1$ lines each contain $m$ integers representing $B_{i,j}$. - The next line contains an integer $q$. - The next $q$ lines each contain four integers $a, b, c, d$ representing a query. ### Output - For each query, print the length of the shortest path. ### Constraints - $1 \le n \times m \le 2 \times 10^4$. - $1 \le A_{i,j}, B_{i,j} \le 10^4$. - $1 \le q \le 10^5$. - $1 \le a, c \le n$. - $1 \le b, d \le m$. ### Example Input: ``` 2 2 4 6 12 8 2 2 2 1 1 2 1 1 2 ``` Output: ``` 12 14 ```