No.867 避難経路

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 29
作問者 : e869120e869120 / テスター : hirakich1000000007hirakich1000000007
1 ProblemId : 3320 / 出題時の順位表

問題文

E869120 君の家は、$H$ 行 $W$ 列のマス目で表されます。上から $i$ 行目、左から $j$ 列目をマス $(i, j)$ とします。左上のマスは $(1, 1)$、右下のマスは $(H, W)$ です。
彼の家において、マス $(i, j)$ の動きにくさの値は $A_{i, j}$ です。
彼は上下左右に隣り合うマスを介して家の中を移動することが出来ます。

さて、レベル $K$ の災害が発生した時、E869120 君がマスを移動するのに以下のような時間がかかります。

  • 彼がマス $(i_1, j_1)$, $(i_2, j_2)$, $(i_3, j_3)$, ..., $(i_G, j_G)$ を順に通ったとする。(開始位置と終了位置も含める)
  • その時、移動に $(K^2+A_{i_1,j_1}) + (K^2+A_{i_2,j_2}) + (K^2+A_{i_3,j_3}) + ... + (K^2+A_{i_G,j_G})$ 秒かかる。
  • 彼は同じマスを二度通ることが出来ない。

彼の家の非常用出口はマス $(gx, gy)$ にあります。以下の $Q$ 個のクエリに答えてください。
  • マス $(x_i, y_i)$ に E869120 君がいるときにレベル $k_i$ の災害が発生した。非常用出口のマスにたどり着き脱出するまでに何秒かかるか?

制約

全ての入力データは以下の制約を満たします。

  • $H$ は $1$ 以上 $250$ 以下の整数である
  • $W$ は $1$ 以上 $250$ 以下の整数である
  • $Q$ は $1$ 以上 $500 \ 000$ 以下の整数である
  • $A_{i, j}$ は $1$ 以上 $99$ 以下の整数である
  • $x_i$ は $1$ 以上 $H$ 以下の整数である
  • $y_i$ は $1$ 以上 $W$ 以下の整数である
  • $k_i$ は $1$ 以上 $1 \ 000 \ 000$ 以下の整数である
  • $gx$ は $1$ 以上 $H$ 以下の整数である
  • $gy$ は $1$ 以上 $W$ 以下の整数である

入力

$H$ $W$
$gx$ $gy$
$A_{1, 1}$ $A_{1, 2}$ $A_{1, 3}$ ... $A_{1, W}$
$A_{2, 1}$ $A_{2, 2}$ $A_{2, 3}$ ... $A_{2, W}$
$A_{3, 1}$ $A_{3, 2}$ $A_{3, 3}$ ... $A_{3, W}$
...
$A_{H, 1}$ $A_{H, 2}$ $A_{H, 3}$ ... $A_{H, W}$
$Q$
$x_1$ $y_1$ $k_1$
$x_2$ $y_2$ $k_2$
$x_3$ $y_3$ $k_3$
...
$x_Q$ $y_Q$ $k_Q$

出力

$Q$ 行に渡って出力してください。
$i$ 行目には、$i$ 回目のクエリに対する答えを出力してください。

サンプル

サンプル1
入力
4 5
1 1
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 4
5
3 1 1
1 1 7
4 5 3
3 2 5
3 5 2
出力
20
52
102
114
54

$1$ 回目のクエリでは、レベル $1$ の災害において、マス $(3, 1)$ から脱出することを考えます。
この場合、マス $(3, 1)$ -> $(2, 1)$ -> $(1, 1)$ と移動すれば $(1^2 + 5) + (1^2 + 9) + (1^2 + 3) = 20$ 秒で脱出できます。

サンプル2
入力
7 7
7 3
1 1 1 1 1 1 1
99 99 99 99 99 99 1
99 1 1 1 1 1 1
99 1 99 99 99 99 99
99 1 1 1 1 1 99
99 99 99 99 99 1 99
99 99 1 1 1 1 99
10
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10
出力
50
125
248
349
430
529
646
781
934
1105
サンプル3
入力
7 7
7 6
1 1 1 1 1 1 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 1 1
2
1 1 4
1 1 5
出力
238
352

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。