結果

問題 No.2354 Poor Sight in Winter
コンテスト
ユーザー flippergo
提出日時 2026-10-14 10:42:34
言語 PyPy3
(8.0.0 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
RE  
実行時間 -
コード長 1,059 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 175 ms
コンパイル使用メモリ 65,260 KB
実行使用メモリ 100,584 KB
最終ジャッジ日時 2026-10-14 10:42:47
合計ジャッジ時間 10,085 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 RE * 8
権限があれば一括ダウンロードができます

ソースコード

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 = -1
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