結果
問題 | No.2695 Warp Zone |
ユーザー |
![]() |
提出日時 | 2024-04-05 00:36:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 225 ms / 2,000 ms |
コード長 | 780 bytes |
コンパイル時間 | 401 ms |
コンパイル使用メモリ | 82,344 KB |
実行使用メモリ | 76,928 KB |
最終ジャッジ日時 | 2024-10-01 00:42:29 |
合計ジャッジ時間 | 4,498 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
H, W, N = map(int, input().split())abcds = [tuple(map(int, input().split())) for _ in range(N)]vs = [(1, 1)] + [(a, b) for a, b, c, d in abcds] + [(c, d) for a, b, c, d in abcds] + [(H, W)]dist = [(1 << 60)] * len(vs)dist[0] = 0done = [False] * len(vs)while True:# Dijkstrav = -1for i in range(len(vs)):if not done[i] and (v == -1 or dist[i] < dist[v]):v = iif v == -1:breakdone[v] = Truex0, y0 = vs[v]d0 = dist[v]for i, (x1, y1) in enumerate(vs):if done[i]:continued = abs(x1 - x0) + abs(y1 - y0)if d0 + d < dist[i]:dist[i] = d0 + dfor i in range(N):dist[N + i + 1] = min(dist[N + i + 1], dist[i + 1] + 1)print(dist[-1])