D - Jumping Takahashi 2 https://atcoder.jp/contests/abc257/tasks/abc257_d

abc257_d.py

from collections import deque


def check(s):
    for i in range(N):
        if bfs(i, s):
            return True
    return False


def bfs(start, s):  # start地点からジャンプ力sで全ての点に到達可能か?
    que = deque([start])
    visits = [False] * N
    visits[start] = True
    while que:
        cur = que.popleft()
        for nxt in range(N):
            if visits[nxt]:
                continue
            if can_jump(cur, nxt, s):
                que.append(nxt)
                visits[nxt] = True
    return all(visits)


def can_jump(i, j, s):  # i番目からj番目のジャンプ台にジャンプできるか?
    xi, yi, pi = points[i]
    xj, yj, pj = points[j]
    return pi * s >= abs(xi - xj) + abs(yi - yj)


N = int(input())
points = []
for i in range(N):
    x, y, P = map(int, input().split())
    points.append((x, y, P))

ng, ok = 0, 10**10
while ok - ng > 1:
    s = (ng + ok) // 2
    if check(s):
        ok = s
    else:
        ng = s

print(ok)