結果
問題 | No.2354 Poor Sight in Winter |
ユーザー |
![]() |
提出日時 | 2023-06-18 21:27:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 519 ms / 2,000 ms |
コード長 | 908 bytes |
コンパイル時間 | 210 ms |
コンパイル使用メモリ | 82,576 KB |
実行使用メモリ | 79,480 KB |
最終ジャッジ日時 | 2024-06-26 08:55:32 |
合計ジャッジ時間 | 7,124 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
from heapq import * # ダイクストラ def dijkstra(k): D = [INF] * (N + 2) D[0] = 0 q = [(0, 0)] while len(q) > 0: d, u = heappop(q) xu, yu = XY[u] # 下のifでTLE解消することがある if d > D[u]: continue for v in range(N + 2): if u == v: continue xv, yv = XY[v] duv = (abs(xu - xv) + abs(yu - yv) - 1) // k if D[v] > D[u] + duv: D[v] = D[u] + duv heappush(q, (D[v], v)) return D[N + 1] N, K = map(int, input().split()) sx, sy, gx, gy = map(int, input().split()) XY = [[sx, sy]] + [list(map(int, input().split())) for _ in range(N)] + [[gx, gy]] INF = 10 ** 6 dmax = abs(sx - gx) + abs(sy - gy) ub = dmax lb = 0 while ub - lb > 1: mid = (lb + ub) // 2 if dijkstra(mid) <= K: ub = mid else: lb = mid print(ub)