結果
問題 |
No.2695 Warp Zone
|
ユーザー |
|
提出日時 | 2024-03-23 14:20:52 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 739 bytes |
コンパイル時間 | 294 ms |
コンパイル使用メモリ | 82,480 KB |
実行使用メモリ | 153,216 KB |
最終ジャッジ日時 | 2024-09-30 13:28:38 |
合計ジャッジ時間 | 13,904 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 WA * 11 |
ソースコード
H,W,N=map(int,input().split()) from collections import defaultdict,deque G=defaultdict(defaultdict) C=defaultdict(int) I=[] O=[] G[(1,1)][(H,W)]=H-1+W-1 for _ in range(N): a,b,c,d=map(int,input().split()) G[(1,1)][(a,b)]=a-1+b-1 G[(1,1)][(c,d)]=c-1+d-1 G[(a,b)][(c,d)]=1 G[(a,b)][(H,W)]=H-a+H-b G[(c,d)][(H,W)]=H-c+W-d C[(a,b)]=1<<60 C[(c,d)]=1<<60 I.append((a,b)) O.append((c,d)) for c,d in O: for a,b in I: G[(c,d)][(a,b)]=abs(c-a)+abs(d-b) C[(H,W)]=1<<60 C[(1,1)]=0 Q=deque() Q.append((1,1)) while Q: a,b=Q.popleft() for c,d in G[(a,b)].keys(): tmp=C[(a,b)]+G[(a,b)][(c,d)] if tmp<C[(c,d)]: C[(c,d)]=tmp Q.append((c,d)) print(C[(H,W)])