TopCoder

Thumb 148522015 226355662574319 5804619006965446972 n
欸我好笨ㄛ
Why am I so weak mie pu

User's AC Ratio

94.4% (34/36)

Submission's AC Ratio

41.0% (59/144)

Description

冒險者萊恩在新手村訓練即將屆滿一年,他詢問師父,什麼時候才能離開新手村,到外面的世界冒險。師父聽聞,拿出一張世界地圖,用手指了地圖的一個位置。

「萊恩,我們在這裡,這是新手村。你想到哪裡去呢?」

萊恩很興奮地說,「聽說迷霧森林很刺激,我想去那裡看看。」

師父又用手指了地圖上另一個位置,「這裡就是迷霧森林。」接著,師父在地圖上雙手揮舞,地圖上開始浮現許多數字。

「哇,好酷喔!師父,這些數字是什麼意思!」

「沒有數字的區域代表無法橫跨的沙漠,數字代表可行經區域裡的怪物等級;如果冒險者的等級低於怪物等級,是沒辦法活著通過那個區域的。」

「啊?!」萊恩很仔細地看著地圖,慢慢地用手指帶出一條路線。「我如果從新手村往北走,再往東走,這樣說起來,我得把我的等級提升到 $5$ 級,才能到得了迷霧森林了。」
目前等級只有 $4$ 級的萊恩低下頭。

「別急,萊恩,看看這裡。」師父抓著萊恩的手指,你可以先往東走,再往北走,然後往西抵達迷霧森林。這條路線,$4$ 級的你就能辦到了。」

「喔耶!謝謝師父!」

真實冒險世界的地圖很大,需要你的幫忙。請你寫一個程式,給定地圖尺寸、新手村和迷霧森林的位置,以及地圖上區域的怪物等級,計算出萊恩最少需要幾等級,才能從新手村出發,安全抵達迷霧森林。

Input Format

  1. 第一行有兩個正整數 $R$ 和 $C$ ($1 \leq R, C \leq 1000$),代表地圖有幾列與幾行。
  2. 第二行有四個整數 $R_s$, $C_s$, $R_d$, $C_d$ ($0 \leq R_s, R_d < R,0 \leq C_s, C_d < C$),其中 $(R_s, C_s)$ 代 表新手村的位置,$(R_d, C_d)$ 代表迷霧森林的位置。新手村和迷霧森林很安全,裡面必定沒有怪物。新手村和迷霧森林不會在同一個位置。
  3. 第三行有一個整數 $N$ $(0 \leq N \leq R\times C$),代表地圖中有幾個可以行經的區域。
  4. 接下去有 $N$ 行,第 $i$ 行有三個整數值 $R_i$, $C_i$, $L_i$ ($0 \leq R_i < R,0 \leq C_i < C,0 \leq L_i \leq 10^ 9$),分別代表區域座標和該區域怪物等級。
  5. 輸入中,任兩個整數間以一個空白隔開。

Output Format

輸出萊恩最少需要為幾等級,才能從新手村出發,平安抵達迷霧森林。(測試資料保
證存在至少一條從新手村到迷霧森林的路。)

Sample Input

輸入範例 1(題目敘述)
6 5
1 1 4 3
18
0 0 2
0 1 3
1 0 1
1 2 1
1 3 4
1 4 2
2 0 3
2 1 2
2 4 4
3 1 3
3 2 5
3 3 2
3 4 3
4 1 3
4 2 5
4 4 2
5 2 2
5 3 2

輸入範例 2
3 4
0 1 1 3
10
2 0 5
2 1 4
2 2 2
2 3 1
1 0 5
1 1 7
1 2 6
0 0 5
0 2 9
0 3 8

Sample Output

輸出範例 1
4
輸出範例 2
5

Hints

本題共有三組測試資料:
第一組測試資料 $1 \leq R, C \leq 10$,新手村到迷霧森林只存在一條路徑,共 $46$ 分。
第二組測試資料 $1 \leq R, C \leq 100$,共 $23$ 分。
第三組測試資料 $1 \leq R, C \leq 1000$,共 $31$ 分。

Problem Source

107北市賽
testdata set by Omelet
110/2/1 修正測資、微調時限及rejudge

Subtasks

No. Testdata Range Constraints Score
1 0~9 $1 \leq R, C \leq 10$,新手村到迷霧森林只存在一條路徑 46
2 0~19 $1 \leq R, C \leq 100$ 23
3 0~29 $1 \leq R, C \leq 1000$ 31

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 600 524288 65536 1 2 3
1 600 524288 65536 1 2 3
2 600 524288 65536 1 2 3
3 600 524288 65536 1 2 3
4 600 524288 65536 1 2 3
5 600 524288 65536 1 2 3
6 600 524288 65536 1 2 3
7 600 524288 65536 1 2 3
8 600 524288 65536 1 2 3
9 600 524288 65536 1 2 3
10 600 524288 65536 2 3
11 600 524288 65536 2 3
12 600 524288 65536 2 3
13 600 524288 65536 2 3
14 600 524288 65536 2 3
15 600 524288 65536 2 3
16 600 524288 65536 2 3
17 600 524288 65536 2 3
18 600 524288 65536 2 3
19 600 524288 65536 2 3
20 600 524288 65536 3
21 600 524288 65536 3
22 600 524288 65536 3
23 600 524288 65536 3
24 600 524288 65536 3
25 600 524288 65536 3
26 600 524288 65536 3
27 600 524288 65536 3
28 600 524288 65536 3
29 600 524288 65536 3