結果
問題 | No.2695 Warp Zone |
ユーザー |
|
提出日時 | 2024-03-22 22:25:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 209 ms / 2,000 ms |
コード長 | 1,093 bytes |
コンパイル時間 | 1,066 ms |
コンパイル使用メモリ | 81,868 KB |
実行使用メモリ | 109,672 KB |
最終ジャッジ日時 | 2024-09-30 11:56:16 |
合計ジャッジ時間 | 4,442 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
import syssys.setrecursionlimit(5*10**5)input = sys.stdin.readlinefrom collections import defaultdict, deque, Counterfrom heapq import heappop, heappushfrom bisect import bisect_left, bisect_rightfrom math import gcdh,w,n = map(int,input().split())za = [list(map(int,input().split())) for i in range(n)]graph = [[] for i in range(n+3)]for i in range(n):ai,bi,ci,di = za[i]for j in range(n):if i == j: continueaj,bj,cj,dj = za[j]dis = abs(ci-aj) + abs(di-bj)graph[i].append((j, dis+1))graph[n].append((i, ai+bi-2))graph[i].append((n+1, abs(h-ci)+abs(w-di)+1))#ダイクストラ法def dijkstra(s,n): # sがスタート、nが頂点数INF = 10**15dist = [INF]*(n+1)que = [(0,s)]dist[s] = 0while que:c,crr = heappop(que)if c > dist[crr]: continuefor nxt, cost in graph[crr]:if dist[crr] + cost < dist[nxt]:dist[nxt] = dist[crr] + costheappush(que,(dist[nxt],nxt))return distd = dijkstra(n,n+2)print(min(d[n+1], h+w-2))