結果

問題 No.867 避難経路
ユーザー nep_pudding3nep_pudding3
提出日時 2019-08-16 23:13:38
言語 PyPy3
(7.3.8)
結果
AC  
実行時間 3,703 ms / 6,000 ms
コード長 1,354 bytes
コンパイル時間 701 ms
使用メモリ 218,516 KB
最終ジャッジ日時 2022-11-22 13:04:47
合計ジャッジ時間 77,074 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 117 ms
76,624 KB
testcase_01 AC 114 ms
76,672 KB
testcase_02 AC 114 ms
76,704 KB
testcase_03 AC 114 ms
76,580 KB
testcase_04 AC 113 ms
76,392 KB
testcase_05 AC 113 ms
76,572 KB
testcase_06 AC 113 ms
76,540 KB
testcase_07 AC 114 ms
76,396 KB
testcase_08 AC 116 ms
76,432 KB
testcase_09 AC 117 ms
76,356 KB
testcase_10 AC 116 ms
76,716 KB
testcase_11 AC 118 ms
76,656 KB
testcase_12 AC 115 ms
76,704 KB
testcase_13 AC 116 ms
76,716 KB
testcase_14 AC 114 ms
76,648 KB
testcase_15 AC 2,831 ms
184,380 KB
testcase_16 AC 3,679 ms
213,840 KB
testcase_17 AC 2,753 ms
180,188 KB
testcase_18 AC 3,356 ms
205,268 KB
testcase_19 AC 3,378 ms
211,424 KB
testcase_20 AC 3,165 ms
203,860 KB
testcase_21 AC 3,703 ms
218,516 KB
testcase_22 AC 3,420 ms
205,724 KB
testcase_23 AC 2,736 ms
182,292 KB
testcase_24 AC 3,443 ms
215,440 KB
testcase_25 AC 3,401 ms
209,204 KB
testcase_26 AC 3,564 ms
211,680 KB
testcase_27 AC 2,961 ms
190,588 KB
testcase_28 AC 1,731 ms
139,664 KB
testcase_29 AC 1,713 ms
139,552 KB
testcase_30 AC 1,260 ms
146,528 KB
testcase_31 AC 1,464 ms
148,696 KB
testcase_32 AC 1,454 ms
149,012 KB
testcase_33 AC 1,481 ms
149,564 KB
testcase_34 AC 1,297 ms
145,688 KB
testcase_35 AC 2,433 ms
203,332 KB
testcase_36 AC 1,340 ms
144,724 KB
testcase_37 AC 1,985 ms
184,860 KB
testcase_38 AC 1,898 ms
176,392 KB
testcase_39 AC 1,698 ms
169,600 KB
testcase_40 AC 1,574 ms
160,860 KB
testcase_41 AC 110 ms
76,524 KB
testcase_42 AC 112 ms
76,512 KB
testcase_43 AC 109 ms
76,396 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
H,W = map(int,input().split())
gx,gy = map(int,input().split())
A = list(list(map(int,input().split()))for i in range(H))
cost = [[[[0,float('inf')]]for i in range(W)]for j in range(H)]
cost[gx-1][gy-1][-1] = [1,A[gx-1][gy-1]]
queue = deque([[gy-1,gx-1]])
while queue != deque([]):
    qx,qy = queue.popleft()
    if qx < W-1 and cost[qy][qx+1][-1][1] > cost[qy][qx][-1][1] + A[qy][qx+1]:
        cost[qy][qx+1].append([cost[qy][qx][-1][0]+1,cost[qy][qx][-1][1] + A[qy][qx+1]])
        queue.append([qx+1,qy])
    if qx > 0 and cost[qy][qx-1][-1][1] > cost[qy][qx][-1][1] + A[qy][qx-1]:
        cost[qy][qx-1].append([cost[qy][qx][-1][0]+1,cost[qy][qx][-1][1] + A[qy][qx-1]])
        queue.append([qx-1,qy])
    if qy > 0 and cost[qy-1][qx][-1][1] > cost[qy][qx][-1][1] + A[qy-1][qx]:
        cost[qy-1][qx].append([cost[qy][qx][-1][0]+1,cost[qy][qx][-1][1] + A[qy-1][qx]])
        queue.append([qx,qy-1])
    if qy < H-1 and cost[qy+1][qx][-1][1] > cost[qy][qx][-1][1] + A[qy+1][qx]:
        cost[qy+1][qx].append([cost[qy][qx][-1][0]+1,cost[qy][qx][-1][1] + A[qy+1][qx]])
        queue.append([qx,qy+1])
Q = int(input())
ans = []
for i in range(Q):
    x,y,k = map(int,input().split())
    hoge = float('inf')
    for a,b in cost[x-1][y-1]:
        hoge = min(a*k**2+b,hoge)
    ans.append(hoge)
for i in ans:
    print(i)
0