結果
問題 | No.2695 Warp Zone |
ユーザー |
|
提出日時 | 2024-06-01 15:24:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 223 ms / 2,000 ms |
コード長 | 869 bytes |
コンパイル時間 | 490 ms |
コンパイル使用メモリ | 82,476 KB |
実行使用メモリ | 109,312 KB |
最終ジャッジ日時 | 2024-12-22 01:08:59 |
合計ジャッジ時間 | 5,056 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
from heapq import heapify, heappop, heappushH, W, N = map(int, input().split())G = [[] for _ in range(2 * N + 2)]G[0].append((2 * N + 1, H - 1 + W - 1))P = []for _ in range(N):a, b, c, d = map(int, input().split())a -= 1; b -= 1; c -= 1; d -= 1P.append((a, b, c, d))for i, (a, b, c, d) in enumerate(P):G[0].append((2 * i + 1, a + b))G[2 * i + 1].append((2 * i + 2, 1))G[2 * i + 2].append((2 * N + 1, H - 1 - c + W - 1 - d))for j, (e, f, g, h) in enumerate(P):if a == e and b == f: continueG[2 * i + 2].append((2 * j + 1, abs(c - e) + abs(d - f)))dist = [10 ** 18] * (2 * N + 2)dist[0] = 0pq = [(0, 0)]heapify(pq)while len(pq) > 0:d, u = heappop(pq)for v, c in G[u]:if dist[v] > dist[u] + c:dist[v] = dist[u] + cheappush(pq, (dist[v], v))print(dist[2 *N + 1])