← 返回题目列表

AtCoder · utpc2012_09

I. 最短路径查询

中文机器翻译题面 查看原题

問題

W \times H 方格,每个方格上都写有一个数字。左上角的正方形 (1, 1),右下方块 表示为 (W, H) 。 来自

质量 从 S 到 T 的路径是一系列方块,其第一个点和最后一个点是 S 和 按字典顺序比较 T ,并且该列中的任何两个连续单元格都是相邻的。这里,相邻意味着共享边缘。路线的成本是路线中所包含的方块中写入的数字的总和。

写在黑板上的数字和 给定 Q 对方块,每对方块 对于 (SX_i, SY_i), (TX_i, TY_i) ,质量 输出一个程序,回答 (SX_i, SY_i) 到 (TX_i, TY_i) 路线的最低成本。


入力

W H Q
A_{1,1} A_{2,1} ... A_{W,1}
...
A_{1,H} A_{2,H} ... A_{W,H}
SX_1 SY_1 TX_1 TY_1
...
SX_Q SY_Q TX_Q TY_Q

输入的第一行包含高度 H 和宽度 W 和查询数量 给出了 Q 。 是

继续 H 行给出了写在板上的编号。 y 线 x 第号 这是写在 A_{x,y} 是质量 给出了 (x, y) 中的数字。

续 在 Q 行中,一对方块 (SX_i, SY_i), (TX_i, TY_i) 被写出。

出力

对于每一行,输出每对方块的路径成本的最小值。 也就是说, 在i 行中,正方形 输出到 (SX_i, SY_i) 到 (TX_i, TY_i) 的路线的最小成本。

制約

  • 1 \leq W \leq 10
  • 2 \leq H \leq 10^4
  • 1 \leq Q \leq 10^5
  • 0 \leq A_{x,y} \leq 10^9
  • 1 \leq SX_i, TX_i \leq W
  • 1 \leq SY_i, TY_i \leq H
  • (SX_i, SY_i) \neq (TX_i, TY_i)

部分点

针对该问题的判断设置了一组50分的测试用例。该组中包含的测试用例输入还满足以下条件。

  • W=2 W \leq 2

入力例 1

2 5 4
0 1
0 1
0 0
1 0
1 0
1 1 2 5
2 1 1 5
1 3 2 3
1 5 1 1

输入示例 1 的输出示例

0
2
0
1

入力例 2

3 6 5
1 9 2
3 4 1
2 5 3
4 2 2
3 1 5
2 6 3
1 1 3 1
1 1 3 6
1 6 3 6
1 3 3 4
2 6 3 2

输入示例 2 的输出示例

11
21
11
10
15