結果
問題 | No.34 砂漠の行商人 |
ユーザー | brthyyjp |
提出日時 | 2021-11-03 02:57:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 290 ms / 5,000 ms |
コード長 | 792 bytes |
コンパイル時間 | 189 ms |
コンパイル使用メモリ | 82,448 KB |
実行使用メモリ | 110,748 KB |
最終ジャッジ日時 | 2024-04-20 15:27:15 |
合計ジャッジ時間 | 3,295 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
54,768 KB |
testcase_01 | AC | 42 ms
54,668 KB |
testcase_02 | AC | 51 ms
64,620 KB |
testcase_03 | AC | 43 ms
55,432 KB |
testcase_04 | AC | 71 ms
76,684 KB |
testcase_05 | AC | 76 ms
76,768 KB |
testcase_06 | AC | 56 ms
68,208 KB |
testcase_07 | AC | 84 ms
76,772 KB |
testcase_08 | AC | 91 ms
78,324 KB |
testcase_09 | AC | 132 ms
83,988 KB |
testcase_10 | AC | 58 ms
73,620 KB |
testcase_11 | AC | 73 ms
76,804 KB |
testcase_12 | AC | 59 ms
69,176 KB |
testcase_13 | AC | 290 ms
110,748 KB |
testcase_14 | AC | 213 ms
96,344 KB |
testcase_15 | AC | 52 ms
66,448 KB |
testcase_16 | AC | 70 ms
76,788 KB |
testcase_17 | AC | 49 ms
64,440 KB |
testcase_18 | AC | 52 ms
65,196 KB |
testcase_19 | AC | 118 ms
82,380 KB |
testcase_20 | AC | 150 ms
87,352 KB |
testcase_21 | AC | 54 ms
68,204 KB |
testcase_22 | AC | 54 ms
67,068 KB |
testcase_23 | AC | 52 ms
64,844 KB |
testcase_24 | AC | 174 ms
90,052 KB |
testcase_25 | AC | 64 ms
74,124 KB |
ソースコード
import sys import io, os input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline n, v, sx, sy, gx, gy = map(int, input().split()) sx, sy = sx-1, sy-1 gx, gy = gx-1, gy-1 L = [] for i in range(n): l = list(map(int, input().split())) L += l s = sy*n+sx g = gy*n+gx from collections import deque q = [(0, v, s)] q = deque(q) HP = [0]*(n*n) HP[s] = v while q: time, hp, i = q.popleft() y, x = divmod(i, n) if i == g: print(time) exit() for dy, dx in (-1, 0), (1, 0), (0, 1), (0, -1): ny, nx = y+dy, x+dx if 0 <= ny < n and 0 <= nx < n: j = ny*n+nx if hp-L[j] <= 0: continue if hp-L[j] > HP[j]: HP[j] = hp-L[j] q.append((time+1, hp-L[j], j)) print(-1)