結果

問題 No.2354 Poor Sight in Winter
コンテスト
ユーザー flippergo
提出日時 2026-10-14 10:49:36
言語 PyPy3
(8.0.0 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WJ  
(最新)
AC  
(最初)
実行時間 -
コード長 1,058 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
最終ジャッジ日時 2026-10-14 10:49:48
ジャッジサーバーID
（参考情報） 		judge3_0 / judge5_0
このコードへのチャレンジ
（要ログイン）

ソースコード

diff #
raw source code 

import heapq
N,K = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
INFTY = 10**6
A = [(sx,sy)]+[tuple(map(int,input().split())) for _ in range(N)]+[(gx,gy)]
low = 0
high = INFTY
while high-low>1:
    mid = (high+low)//2
    G = {i:{} for i in range(N+2)}
    for i in range(N+1):
        xi,yi = A[i]
        for j in range(i+1,N+2):
            xj,yj = A[j]
            d = abs(xj-xi)+abs(yj-yi)
            if d<=mid:
                G[i][j] = 0
                G[j][i] = 0
            else:
                G[i][j] = (d+mid-1)//mid-1
                G[j][i] = (d+mid-1)//mid-1
    dist = [INFTY]*(N+2)
    dist[0] = 0
    visited = [False]*(N+2)
    heap = [(0,0)]
    while heap:
        d,i = heapq.heappop(heap)
        if d>dist[i]:continue
        visited[i] = True
        for j in G[i]:
            if visited[j]:continue
            d1 = G[i][j]
            if dist[j]>d+d1:
                dist[j] = d+d1
                heapq.heappush(heap,(d+d1,j))
    if dist[N+1]<=K:
        high = mid
    else:
        low = mid
print(high)
0