TLEoj Contest #11 - Người hướng nội và cuộc đi dạo vui vẻ

Điểm: 1800 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

_nhphuc

Dạng bài

Bocchi là một cô gái hướng nội, mẹ của cô bé – cô Michiyo Gotoh không thích điều này. Vì vậy, mỗi ngày mẹ của cô bé đều bắt cô bé chạy quanh khu phố qua ít nhất k con đường trong khu phố sau đó trở về điểm bắt đầu (lưu ý là trên đường đi và về chỉ cần có ít nhất k con đường, hay nói cách khác cô có thể đi lại trên một con đường nhiều lần), khu phố của Bocchi có dạng một lưới các nhà dân có kích thước n x m, với một khu nhà ( $i_1$ , $j_1$ ) sẽ có đường nối tới khu nhà ( $i_2$ , $j_2$ ) nếu | $i_1$ – $i_2$ | + | $j_1$ – $j_2$ | $=$ $1$ . Dù các con đường có chiều dài bằng nhau nhưng để đi hết mỗi con đường sẽ tiêu tốn một khoảng thời gian có thể khác nhau vì có thể các con đường trên có chó dữ, đông người hay Oppenheimer đang thử bom nguyên tử,…
Tuy nhiên, Bocchi được quyền chọn một điểm bắt đầu cho chặng đường của cô, và cô muốn tối thiểu thời gian chạy nhất có thể, Bocchi sẽ hỏi bạn $q$ lần dạng câu hỏi nếu bắt đầu chạy từ khu nhà ( $i$ , $j$ ) thì cần tối thiểu bao nhiêu thời gian, nhiệm vụ của bạn là trả lời cho Bocchi để giúp tay rock của chúng ta có thời gian chạy ít nhất có thể.

Input, Output and Scoring

Input

Dòng đầu tiên gồm ba số $n$ , $m$ , $k$ - số dòng, số cột của khu phố và số con đường mà Bocchi phải đi qua. ( $n, m, k\leq 200$ )
$n$ dòng tiếp theo mỗi dòng chứa $m – 1$ số, với số thứ $j$ trong dòng $i$ là thời gian đi con đường từ ( $i$ , $j$ ) tới ( $i$ , $j + 1$ ) đảm bảo thời gian đi trên một con đường không vượt quá $10^6$
$n – 1$ dòng tiếp theo mỗi dòng chứa $m$ số, với số thứ $j$ trong dòng $i$ là thời gian đi con đường từ ( $i$ , $j$ ) tới ( $i + 1$ , $j$ ) đảm bảo thời gian đi trên một con đường không vượt quá $10^6$
Dòng tiếp theo chứa một số nguyên $q$ – số lượng truy vấn ( $q\leq 10^6$ )
$q$ dòng tiếp theo mỗi dòng chứa một cặp số nguyên ( $i$ , $j$ ) – nếu Bocchi xuất phát từ ( $i$ , $j$ ) thì thời gian ngắn nhất là bao nhiêu ?

Output

Gồm $q$ dòng mỗi dòng chứa kết quả của mỗi truy vấn.

Scoring

Subtask $1$ $(30\%)$ : $n$ , $m$ , $k$ , $q\leq 10$
Subtask $2$ $(70\%)$ : Không có ràng buộc gì thêm.

Test 1

Input

Output

Note

Dù đi theo phương án nào thì Bocchi cũng tốn $10$ đơn vị thời gian.

Test 2

Input

Output

Note

Bocchi chỉ cần đi qua lại hai khu nhà $(1, 1)$ và $(1, 2)$ trong $4$ lần với $4$ đơn vị thời gian.

Bình luận

Không có bình luận nào.