题目详情题解（0）讨论（0）提交记录（0）

AT_utpc2012_09.最短路クエリ

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在 W×HW \times H 的网状棋盘上,每一格都标有一个数字。左上和右下的格子分别用 (1,1)(1, 1) 和 (W,H)(W, H) 表示。

从格点 SS 到格点 TT 的路径指由格子构成的一个序列，其中起点和终点分别为 S,TS, T，并且在该序列中，任意两个连续的格子都是邻接的。两个格子是邻接的，当且仅当格子有公共边。一条路径的长度，是指所经过的格子上的数字之和。

给出棋盘上每一格上的数字，和 QQ 个数对 (SXi,SYi)(SX_i,SY_i) 和 (TXi,TYi)(TX_i,TY_i)。请你写一个程序，算出从 (SXi,SYi)(SX_i, SY_i) 到 (TXi,TYi)(TX_i, TY_i) 的最短路径。

输入格式

第一行有三个数，分别是宽度 WW、高度 HH 和询问个数 QQ。

接下来的 HH 行，每行 MM 个数，其中第 xx 行第 yy 列的数表示棋盘上格子 (x,y)(x, y) 上标的数 Ax,yA_{x, y}。

再下面最后的 QQ 行，每行 44 个数，表示数对 (SXi,SYi)(SX_i, SY_i)，(TXi,TYi)(TX_i, TY_i)。

输出格式

共 QQ 行，第 ii 行输出从 (SXi,SYi)(SX_i, SY_i) 到 (TXi,TYi)(TX_i, TY_i) 的最短路径的长度。

输入输出样例

  • 输入#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

说明/提示

对 50%50\% 的数据，有 W≤2W \le 2。

对 100%100\% 的数据，有：

  • 1≤W≤101 \le W \le 10
  • 2≤H≤1042 \le H \le 10^4
  • 1≤Q≤1051 \le Q \le 10^5
  • 0≤Ax,y≤1090 \le A_{x, y} \le 10^9
  • 1≤SXi,TXi≤W1 \le SX_i, TX_i \le W
  • 1≤SYi,TYi≤H1 \le SY_i, TY_i \le H
  • (SXi,SYi)≠(TXi,TYi)(SX_i, SY_i) \neq (TX_i, TY_i)

输入解题思路，AI测评打分。不知道怎么写?

首页