ABC257D - Jumping Takahashi 2

考え方

答え（$S$）で二分探索（$O(\log \cdots)$）する．

$S$を決めれば辺を$O(N^{2})$で張れる．

スタート地点（$N$通り）を決めれば，BFS（$O(N^{2})$）で全ての頂点に行けるかどうかを計算できる．

回答例

すでに訪れた頂点はリストではなくsetで管理する（最短経路問題 - 競プロはじめました）．

頂点を訪れた記録は，キューから取り出すときに行うとTLEした．キューに入れるときに記録すると間に合う．

from collections import deque

N = int(input())
xyP = [list(map(int, input().split())) for _ in range(N)]

def f(S):
    G = [[] for _ in range(N)]
    for i in range(N):
        xi, yi, Pi = xyP[i]
        for j in range(N):
            xj, yj, Pj = xyP[j]
            if Pi * S >= abs(xi - xj) + abs(yi - yj):
                G[i].append(j)
    for i in range(N):
        q = deque([i])
        seen = set([i])
        while q:
            cur = q.popleft()
            for chi in G[cur]:
                if chi not in seen:
                    q.append(chi)
                    seen.add(chi)
        if len(seen) == N:
            return True
    return False            

ok = 10 ** 10
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid

print(ok)