結果
問題 | No.1638 Robot Maze |
ユーザー | harurun |
提出日時 | 2021-06-28 11:49:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 228 ms / 2,000 ms |
コード長 | 2,514 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 81,832 KB |
実行使用メモリ | 81,832 KB |
最終ジャッジ日時 | 2023-10-17 02:24:42 |
合計ジャッジ時間 | 7,788 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
53,560 KB |
testcase_01 | AC | 39 ms
53,560 KB |
testcase_02 | AC | 38 ms
53,620 KB |
testcase_03 | AC | 128 ms
80,644 KB |
testcase_04 | AC | 41 ms
55,612 KB |
testcase_05 | AC | 40 ms
55,612 KB |
testcase_06 | AC | 42 ms
55,612 KB |
testcase_07 | AC | 40 ms
55,612 KB |
testcase_08 | AC | 42 ms
55,612 KB |
testcase_09 | AC | 40 ms
55,612 KB |
testcase_10 | AC | 40 ms
55,612 KB |
testcase_11 | AC | 41 ms
55,612 KB |
testcase_12 | AC | 40 ms
55,612 KB |
testcase_13 | AC | 41 ms
55,612 KB |
testcase_14 | AC | 146 ms
79,184 KB |
testcase_15 | AC | 119 ms
78,632 KB |
testcase_16 | AC | 116 ms
78,492 KB |
testcase_17 | AC | 120 ms
78,660 KB |
testcase_18 | AC | 67 ms
73,064 KB |
testcase_19 | AC | 114 ms
78,476 KB |
testcase_20 | AC | 116 ms
78,480 KB |
testcase_21 | AC | 83 ms
78,012 KB |
testcase_22 | AC | 81 ms
77,772 KB |
testcase_23 | AC | 84 ms
78,012 KB |
testcase_24 | AC | 83 ms
78,012 KB |
testcase_25 | AC | 83 ms
78,012 KB |
testcase_26 | AC | 91 ms
78,116 KB |
testcase_27 | AC | 91 ms
78,116 KB |
testcase_28 | AC | 94 ms
78,092 KB |
testcase_29 | AC | 91 ms
78,092 KB |
testcase_30 | AC | 39 ms
53,564 KB |
testcase_31 | AC | 40 ms
53,564 KB |
testcase_32 | AC | 140 ms
79,432 KB |
testcase_33 | AC | 164 ms
80,180 KB |
testcase_34 | AC | 165 ms
81,272 KB |
testcase_35 | AC | 164 ms
79,684 KB |
testcase_36 | AC | 176 ms
81,264 KB |
testcase_37 | AC | 146 ms
79,436 KB |
testcase_38 | AC | 160 ms
79,852 KB |
testcase_39 | AC | 181 ms
81,832 KB |
testcase_40 | AC | 174 ms
80,820 KB |
testcase_41 | AC | 168 ms
81,088 KB |
testcase_42 | AC | 185 ms
81,012 KB |
testcase_43 | AC | 228 ms
81,736 KB |
testcase_44 | AC | 218 ms
81,720 KB |
testcase_45 | AC | 210 ms
81,500 KB |
testcase_46 | AC | 183 ms
81,660 KB |
testcase_47 | AC | 171 ms
80,692 KB |
testcase_48 | AC | 178 ms
81,404 KB |
testcase_49 | AC | 152 ms
79,996 KB |
testcase_50 | AC | 175 ms
80,836 KB |
testcase_51 | AC | 190 ms
81,232 KB |
ソースコード
import sys class dijkstra: def __init__(self,V): self.INF=float("inf") self.G=[[] for _ in [0]*V] self.V=V return def add1(self,s,t,v): self.G[s].append([t,v]) return def add2(self,s,t,v): self.G[s].append([t,v]) self.G[t].append([s,v]) return def run(self,s): from heapq import heapify,heappop,heappush ret=[self.INF]*self.V que=[] heapify(que) ret[s]=0 heappush(que,(0,s)) while que: p=heappop(que) v=p[1] if ret[v]<p[0]: continue for i in range(len(self.G[v])): e=self.G[v][i] if ret[e[0]]>ret[v]+e[1]: ret[e[0]]=ret[v]+e[1] heappush(que,(ret[e[0]],e[0])) return ret def main(): H,W=map(int,input().split()) assert(2<=H<=100) assert(2<=W<=100) U,D,R,L,K,P=map(int,input().split()) assert(0<=U<=100) assert(0<=D<=100) assert(0<=R<=100) assert(0<=L<=100) assert(0<=K<=10**13) assert(0<=P<=10**9) xs,ys,xt,yt=map(int,input().split()) assert(1<=xs<=H) assert(1<=ys<=W) assert(1<=xt<=H) assert(1<=yt<=W) assert((xs,ys)!=(xt,yt)) xs-=1 ys-=1 xt-=1 yt-=1 C=[] for i in range(H): S=input()+"#" assert(len(S)==W+1) for j in S: assert(j in[".","@","#"]) C.append(S) C.append("#"*W) assert(C[xs][ys]==".") assert(C[xt][yt]==".") ijk=dijkstra(H*W) U*=2 D*=2 R*=2 L*=2 K*=2 for i in range(H): for j in range(W): if C[i][j]=="#": continue if C[i][j]=="@": if C[i+1][j]==".": ijk.add1(W*i+j,W*(i+1)+j,P+D) ijk.add1(W*(i+1)+j,W*i+j,P+U) elif C[i+1][j]=="@": ijk.add1(W*i+j,W*(i+1)+j,2*P+D) ijk.add1(W*(i+1)+j,W*i+j,2*P+U) if C[i][j+1]==".": ijk.add1(W*i+j,W*i+j+1,P+R) ijk.add1(W*i+j+1,W*i+j,P+L) elif C[i][j+1]=="@": ijk.add1(W*i+j,W*i+j+1,2*P+R) ijk.add1(W*i+j+1,W*i+j,2*P+L) else: if C[i+1][j]==".": ijk.add1(W*i+j,W*(i+1)+j,D) ijk.add1(W*(i+1)+j,W*i+j,U) elif C[i+1][j]=="@": ijk.add1(W*i+j,W*(i+1)+j,P+D) ijk.add1(W*(i+1)+j,W*i+j,P+U) if C[i][j+1]==".": ijk.add1(W*i+j,W*i+j+1,R) ijk.add1(W*i+j+1,W*i+j,L) elif C[i][j+1]=="@": ijk.add1(W*i+j,W*i+j+1,P+R) ijk.add1(W*i+j+1,W*i+j,P+L) d=ijk.run(W*xs+ys) if d[W*xt+yt]<=K: print("Yes") else: print("No") sys.stderr.write(f"ans:{d[W*xt+yt]//2}\n") return main()