結果
問題 | No.2354 Poor Sight in Winter |
ユーザー |
![]() |
提出日時 | 2023-06-16 22:00:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 351 ms / 2,000 ms |
コード長 | 776 bytes |
コンパイル時間 | 746 ms |
コンパイル使用メモリ | 82,696 KB |
実行使用メモリ | 80,732 KB |
最終ジャッジ日時 | 2024-06-24 14:10:31 |
合計ジャッジ時間 | 5,867 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
from heapq import heappop,heappush n,k = map(int,input().split()) sx,sy,gx,gy = map(int,input().split()) xy = [(sx,sy)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy)] dist = [[0]*(n+2) for _ in range(n+2)] for i,(ix,iy) in enumerate(xy): for j,(jx,jy) in enumerate(xy): dist[i][j] = abs(ix-jx)+abs(iy-jy) ng = 0; ok = dist[0][n+1] while ok-ng>1: mid = (ng+ok)//2 d = [0]+[10**9]*(n+1); f = [False]*(n+2); hq = [(0,0)] while hq: _,p = heappop(hq) if f[p]: continue f[p] = True for i in range(n+2): if p!=i and d[i]>d[p]+(dist[p][i]-1)//mid: d[i] = d[p]+(dist[p][i]-1)//mid heappush(hq,(d[p]+(dist[p][i]-1)//mid,i)) if d[n+1]<=k: ok = mid else: ng = mid print(ok)