結果
問題 | No.2695 Warp Zone |
ユーザー | tkykwtnb |
提出日時 | 2024-03-23 14:20:52 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 739 bytes |
コンパイル時間 | 406 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 152,216 KB |
最終ジャッジ日時 | 2024-03-23 14:21:09 |
合計ジャッジ時間 | 16,414 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
55,476 KB |
testcase_01 | AC | 41 ms
55,476 KB |
testcase_02 | AC | 42 ms
55,476 KB |
testcase_03 | WA | - |
testcase_04 | AC | 1,356 ms
146,584 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | AC | 1,477 ms
152,216 KB |
testcase_08 | AC | 65 ms
70,356 KB |
testcase_09 | AC | 469 ms
98,548 KB |
testcase_10 | WA | - |
testcase_11 | AC | 174 ms
82,600 KB |
testcase_12 | AC | 733 ms
113,248 KB |
testcase_13 | AC | 41 ms
55,476 KB |
testcase_14 | WA | - |
testcase_15 | AC | 452 ms
96,768 KB |
testcase_16 | AC | 158 ms
81,556 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 974 ms
127,416 KB |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | AC | 40 ms
55,476 KB |
testcase_25 | AC | 40 ms
55,476 KB |
testcase_26 | AC | 40 ms
55,476 KB |
ソースコード
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)])