結果
問題 | No.2695 Warp Zone |
ユーザー | tkykwtnb |
提出日時 | 2024-03-23 14:13:16 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 746 bytes |
コンパイル時間 | 396 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 151,996 KB |
最終ジャッジ日時 | 2024-03-23 14:13:33 |
合計ジャッジ時間 | 16,312 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
55,476 KB |
testcase_01 | AC | 41 ms
55,476 KB |
testcase_02 | AC | 43 ms
55,476 KB |
testcase_03 | WA | - |
testcase_04 | AC | 1,319 ms
146,108 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | AC | 1,467 ms
151,356 KB |
testcase_08 | AC | 66 ms
70,356 KB |
testcase_09 | AC | 471 ms
98,444 KB |
testcase_10 | WA | - |
testcase_11 | AC | 178 ms
82,476 KB |
testcase_12 | AC | 716 ms
113,148 KB |
testcase_13 | AC | 42 ms
55,476 KB |
testcase_14 | WA | - |
testcase_15 | AC | 448 ms
96,660 KB |
testcase_16 | AC | 155 ms
81,436 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 964 ms
126,816 KB |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | AC | 41 ms
55,476 KB |
testcase_25 | AC | 40 ms
55,476 KB |
testcase_26 | AC | 42 ms
55,476 KB |
ソースコード
H,W,N=map(int,input().split()) from collections import defaultdict,deque G=defaultdict(dict) 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)]=min(C[(c,d)],tmp) Q.append((c,d)) print(C[(H,W)])