{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n\t\t\t\n\t\t\t\u003ch3\u003e問題\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\n\u003cvar\u003e\\(W \\times H\\)\u003c/var\u003e のグリッド状に区切られた盤面があり,各マスには数字が書かれている.左上のマスを \u003cvar\u003e\\((1, 1)\\)\u003c/var\u003e,右下のマスを \u003cvar\u003e\\((W, H)\\)\u003c/var\u003e と表す.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nマス \u003cvar\u003e\\(S\\)\u003c/var\u003e からマス \u003cvar\u003e\\(T\\)\u003c/var\u003e への経路とは,マスの列であって,最初と最後が \u003cvar\u003e\\(S\\)\u003c/var\u003e と \u003cvar\u003e\\(T\\)\u003c/var\u003e であり,かつ列において連続する任意の 2 つのマスは隣接しているようなものである.ここで,隣接するとは,辺を共有することを指す.経路のコストとは,経路に含まれるマスに書かれている数字の合計である.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\n盤面に書かれた数字と \u003cvar\u003e\\(Q\\)\u003c/var\u003e 個のマスの対が与えられたとき,各マスの対 \u003cvar\u003e\\((SX_i, SY_i), (TX_i, TY_i)\\)\u003c/var\u003e に対し,マス \u003cvar\u003e\\((SX_i, SY_i)\\)\u003c/var\u003e からマス \u003cvar\u003e\\((TX_i, TY_i)\\)\u003c/var\u003e への経路のコストの最小値を答えるプログラムを出力せよ.\r\n\u003c/p\u003e\r\n\r\n\u003chr\u003e\r\n\r\n\u003ch3\u003e入力\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\n\u003cvar\u003e\\(W\\)\u003c/var\u003e \u003cvar\u003e\\(H\\)\u003c/var\u003e \u003cvar\u003e\\(Q\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(A_{1,1}\\)\u003c/var\u003e \u003cvar\u003e\\(A_{2,1}\\)\u003c/var\u003e \u003cvar\u003e\\(...\\)\u003c/var\u003e \u003cvar\u003e\\(A_{W,1}\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(...\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(A_{1,H}\\)\u003c/var\u003e \u003cvar\u003e\\(A_{2,H}\\)\u003c/var\u003e \u003cvar\u003e\\(...\\)\u003c/var\u003e \u003cvar\u003e\\(A_{W,H}\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(SX_1\\)\u003c/var\u003e \u003cvar\u003e\\(SY_1\\)\u003c/var\u003e \u003cvar\u003e\\(TX_1\\)\u003c/var\u003e \u003cvar\u003e\\(TY_1\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(...\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(SX_Q\\)\u003c/var\u003e \u003cvar\u003e\\(SY_Q\\)\u003c/var\u003e \u003cvar\u003e\\(TX_Q\\)\u003c/var\u003e \u003cvar\u003e\\(TY_Q\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\r\n\u003cp\u003e\r\n入力の最初の行には,縦幅 \u003cvar\u003e\\(H\\)\u003c/var\u003e と横幅 \u003cvar\u003e\\(W\\)\u003c/var\u003e とクエリの個数 \u003cvar\u003e\\(Q\\)\u003c/var\u003e が与えられる.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\n続く \u003cvar\u003e\\(H\\)\u003c/var\u003e 行には,盤面に書かれている数字が与えられる.\r\n\u003cvar\u003e\\(y\\)\u003c/var\u003e 行目の \u003cvar\u003e\\(x\\)\u003c/var\u003e 個目の数字 \u003cvar\u003e\\( A_{x,y} \\)\u003c/var\u003e はマス \u003cvar\u003e\\((x, y)\\)\u003c/var\u003e に書かれた数字である.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nさらに続く \u003cvar\u003e\\(Q\\)\u003c/var\u003e 行に,マスの対 \u003cvar\u003e\\((SX_i, SY_i), (TX_i, TY_i)\\)\u003c/var\u003e が書かれている.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003e出力\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\n各行に,各マスの対に対する経路のコストの最小値を出力せよ.\r\n即ち,\u003cvar\u003e\\(i\\)\u003c/var\u003e 行目に,マス \u003cvar\u003e\\((SX_i, SY_i)\\)\u003c/var\u003e からマス \u003cvar\u003e\\((TX_i, TY_i)\\)\u003c/var\u003e への経路のコストの最小値を出力せよ.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003e制約\u003c/h3\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003e \u003cvar\u003e\\( 1 \\leq W \\leq 10 \\)\u003c/var\u003e\u003c/li\u003e\r\n\r\n\u003cli\u003e \u003cvar\u003e\\( 2 \\leq H \\leq 10^4 \\)\u003c/var\u003e\u003c/li\u003e\r\n\r\n\u003cli\u003e \u003cvar\u003e\\( 1 \\leq Q \\leq 10^5 \\)\u003c/var\u003e\u003c/li\u003e\r\n\r\n\u003cli\u003e \u003cvar\u003e\\( 0 \\leq A_{x,y} \\leq 10^9 \\)\u003c/var\u003e\u003c/li\u003e\r\n\r\n\u003cli\u003e \u003cvar\u003e\\( 1 \\leq SX_i, TX_i \\leq W \\)\u003c/var\u003e\u003c/li\u003e\r\n\r\n\u003cli\u003e \u003cvar\u003e\\( 1 \\leq SY_i, TY_i \\leq H \\)\u003c/var\u003e\u003c/li\u003e\r\n\r\n\u003cli\u003e \u003cvar\u003e\\( (SX_i, SY_i) \\neq (TX_i, TY_i) \\)\u003c/var\u003e\u003c/li\u003e\r\n\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003e部分点\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\nこの問題の判定には,50 点分のテストケースのグループが設定されている. このグループに含まれるテストケースの入力は追加で以下の条件を満たす. \r\n\u003c/p\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003e \u003cs\u003e\u003cvar\u003e\\(W\u003d2\\)\u003c/var\u003e\u003c/s\u003e \u003cbig\u003e\u003cb\u003e\u003cfont color\u003d\"red\"\u003e\u003cvar\u003e\\(W \\leq 2\\)\u003c/var\u003e\u003c/font\u003e\u003c/b\u003e\u003c/big\u003e\u003c/li\u003e\r\n\r\n\u003c/ul\u003e\r\n\r\n\u003chr\u003e\r\n\r\n\u003ch3\u003e入力例 1\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\n2 5 4\r\n0 1\r\n0 1\r\n0 0\r\n1 0\r\n1 0\r\n1 1 2 5\r\n2 1 1 5\r\n1 3 2 3\r\n1 5 1 1\r\n\u003c/pre\u003e\r\n\r\n\u003ch3\u003e入力例 1 に対する出力例\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\n0\r\n2\r\n0\r\n1\r\n\u003c/pre\u003e\r\n\r\n\u003chr\u003e\r\n\r\n\u003ch3\u003e入力例 2\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\n3 6 5\r\n1 9 2\r\n3 4 1\r\n2 5 3\r\n4 2 2\r\n3 1 5\r\n2 6 3\r\n1 1 3 1\r\n1 1 3 6\r\n1 6 3 6\r\n1 3 3 4\r\n2 6 3 2\r\n\u003c/pre\u003e\r\n\r\n\u003ch3\u003e入力例 2 に対する出力例\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\n11\r\n21\r\n11\r\n10\r\n15\r\n\u003c/pre\u003e\n\t\t"}}]}