結果
問題 | No.2695 Warp Zone |
ユーザー |
|
提出日時 | 2024-03-22 21:47:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 316 ms / 2,000 ms |
コード長 | 1,175 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 82,784 KB |
実行使用メモリ | 91,376 KB |
最終ジャッジ日時 | 2024-09-30 11:16:29 |
合計ジャッジ時間 | 6,690 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
import collections,sys,math,functools,operator,itertools,bisect,heapq,decimal,string,time,random#sys.setrecursionlimit(10**9)#sys.set_int_max_str_digits(0)input = sys.stdin.readline#n = int(input())#alist = list(map(int,input().split()))#alist = []#s = input()h,w,n = map(int,input().split())v = 2*n+2e = [[] for i in range(2*n+2)]warp = []warp.append((1,1))for i in range(n):a,b,c,d = map(int,input().split())dist = abs(a-c) + abs(b-d)#e[2*i+2].append(2*i+1)e[2*i+1].append(2*i+2)warp.append((a,b))warp.append((c,d))warp.append((h,w))start = 0d = []dist = [10**18 for i in range(v)]heapq.heappush(d,(0,start))dist[start] = 0while d:_,now = heapq.heappop(d)if _ > dist[now]:continuex,y = warp[now]for to in e[now]:if dist[to] > dist[now] + 1:dist[to] = dist[now] + 1heapq.heappush(d,(dist[to],to))for i in range(v):if i == now:continuetx,ty = warp[i]cost = abs(x-tx) + abs(y-ty)if dist[i] > dist[now] + cost:dist[i] = dist[now] + costheapq.heappush(d,(dist[i],i))print(dist[-1])