結果

問題 No.2354 Poor Sight in Winter
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:19:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 311 ms / 2,000 ms
コード長 2,494 bytes
コンパイル時間 292 ms
コンパイル使用メモリ 82,192 KB
実行使用メモリ 81,460 KB
最終ジャッジ日時 2025-03-31 17:20:04
合計ジャッジ時間 4,768 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque
import heapq

def main():
    N, K = map(int, sys.stdin.readline().split())
    sx, sy, gx, gy = map(int, sys.stdin.readline().split())
    landmarks = []
    existing = set()
    existing.add((sx, sy))
    existing.add((gx, gy))
    for _ in range(N):
        x, y = map(int, sys.stdin.readline().split())
        landmarks.append((x, y))
        existing.add((x, y))
    nodes = [(sx, sy), (gx, gy)] + landmarks
    M = len(nodes)
    # Precompute d_matrix
    d_matrix = [[0] * M for _ in range(M)]
    for i in range(M):
        for j in range(i+1, M):
            dx = abs(nodes[i][0] - nodes[j][0])
            dy = abs(nodes[i][1] - nodes[j][1])
            d = dx + dy
            d_matrix[i][j] = d
            d_matrix[j][i] = d
    # Initial binary search bounds
    initial_high = d_matrix[0][1]
    low = 1
    high = initial_high
    answer = initial_high
    while low <= high:
        mid = (low + high) // 2
        # BFS step to check connectivity with existing nodes and edges <= mid
        visited = [False]*M
        q = deque()
        q.append(0)
        visited[0] = True
        found = False
        while q:
            u = q.popleft()
            if u == 1:
                found = True
                break
            for v in range(M):
                if u != v and not visited[v] and d_matrix[u][v] <= mid:
                    visited[v] = True
                    q.append(v)
        if found:
            answer = mid
            high = mid -1
            continue
        # Dijkstra's algorithm
        heap = []
        dist = [float('inf')] * M
        dist[0] = 0
        heapq.heappush(heap, (0, 0))
        while heap:
            current_cost, u = heapq.heappop(heap)
            if u == 1:
                break
            if current_cost > dist[u]:
                continue
            for v in range(M):
                if u == v:
                    continue
                d = d_matrix[u][v]
                if d ==0:
                    continue  # shouldn't happen
                required = (d + mid -1) // mid -1
                if d <= mid:
                    required = 0
                if dist[v] > dist[u] + required:
                    dist[v] = dist[u] + required
                    heapq.heappush(heap, (dist[v], v))
        if dist[1] <= K:
            answer = mid
            high = mid -1
        else:
            low = mid +1
    print(answer)

if __name__ == "__main__":
    main()
0