結果
問題 | No.2695 Warp Zone |
ユーザー |
![]() |
提出日時 | 2024-03-22 21:40:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,208 ms / 2,000 ms |
コード長 | 943 bytes |
コンパイル時間 | 170 ms |
コンパイル使用メモリ | 82,288 KB |
実行使用メモリ | 427,752 KB |
最終ジャッジ日時 | 2024-09-30 11:09:05 |
合計ジャッジ時間 | 12,808 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
H,W,N=map(int,input().split()) dic={} dic[(1,1)]=0 dic[(H,W)]=1 num=2 pos=[(1,1),(H,W)] abcd=[] for i in range(N): a,b,c,d=map(int,input().split()) if (a,b) not in dic: dic[(a,b)]=num pos.append((a,b)) num+=1 if (c,d) not in dic: dic[(c,d)]=num pos.append((c,d)) num+=1 abcd.append([a,b,c,d]) M=num edge=[[] for i in range(M)] for a,b,c,d in abcd: edge[dic[(a,b)]].append((dic[c,d],1)) for i in range(M): for j in range(M): xi,yi=pos[i] xj,yj=pos[j] edge[i].append([j,abs(xi-xj)+abs(yi-yj)]) from heapq import heappush, heappop INF=10**18 def dijkstra(start,n): dist=[INF]*n hq=[(0,start)] dist[start]=0 seen=[False]*n while hq: w,v=heappop(hq) if dist[v]<w: continue seen[v]=True for to,cost in edge[v]: if seen[to]==False and dist[v]+cost<dist[to]: dist[to]=dist[v]+cost heappush(hq,(dist[to],to)) return dist print(dijkstra(0,M)[1])