\(O(N^2)\) 時間の解法を紹介します。

この問題は、全てのジャンプ台間で必要な \(S\) の値を計算しておくと、根が任意で、辺の重みの総和を取る代わりに辺の重みの max を取る、密グラフにおける最小有向全域木の問題と見ることができます。

通常の (密グラフにおける) 最小有向全域木問題は Chu–Liu/Edmonds’ algorithm によって \(O(N^2)\) で解くことができます。この問題も、このアルゴリズムに近い方法で \(O(N^2)\) で解くことができます。

\(N\) 頂点の重み付き有向グラフとして話を進めます。頂点 \(i\) から頂点 \(j\) に行く辺のコストは \(\displaystyle\text{cost}(i, j) = \left\lceil\frac{|x_i - x_j| + |y_i - y_j|}{P_i}\right\rceil\) です。

\(G\) を \(N\) 頂点 \(0\) 辺の有向グラフとし、これに辺を加えて目的の最小有向全域木を作ることを考えます。

有向全域木では、根以外の頂点には入る辺が \(1\) 本、根には入る辺が \(0\) 本あります。 そこで、各頂点について、入る辺のうち最もコストの小さい辺を選び、選ばれた \(N\) 本の辺のうちコストが最大のものを除いた \(N - 1\) 本を \(G\) に採用してみます。答えは採用した辺のコスト以上になります。(有向全域木となる必要条件 (入次数が \(1\) の頂点が \(N - 1\) 個) を満たすコスト最小の辺を採用したため)

\(G\) はどのようなグラフになっているでしょうか？

入次数が \(0\) の頂点を \(r\) とします。\(r\) を含む弱連結成分では、\(r\) を根とする有向木になります。(向きを無視すると \(n\) 頂点 \(n-1\) 辺の連結グラフなので木になって、\(r\) の入次数が \(0\) 、それ以外の入次数が \(1\) であることから向きが決まる)
\(r\) を含まない弱連結成分では、\(2\) 頂点以上からなるサイクルに、それを根とする有向木が \(0\) 個以上繋がった形をしています。(連結な functional graph)

もし、\(r\) を含まない弱連結成分が存在しなければ、\(G\) は目的の最小有向全域木です。\(r\) を含まない弱連結成分が存在する場合、そのサイクル部分に注目します。\(G\) を有向全域木とするためには、サイクルから辺を \(1\) 本取り除かなければなりませんが、今回はどの辺のコストも答え以下であることが保証されていて、有向全域木を \(1\) つ含んでいれば辺が多い分には問題ないので、辺は取り除かないことにします。(最後にうまく辺を取り除いて有向全域木を構成することもできます。)

サイクル部分 (強連結成分) は、サイクル内の頂点から辺を張るならばどの頂点から張っても、サイクル内の頂点へ辺を張るならばどの頂点へ張っても、頂点間の到達可能性の観点では同じことです。サイクル全体が \(1\) つの頂点として扱えるので、\(1\) つの頂点に縮約してしまいましょう。

サイクルの頂点を \(c_1, c_2, \dots, c_k\) 、縮約した新しい頂点を \(c\) とすると、\(\displaystyle\text{cost}(x, c) = \min_{i=1}^k\{\text{cost}(x, c_i)\},\ \text{cost}(c, x) = \min_{i=1}^k\{\text{cost}(c_i, x)\}\) となります。

これで頂点数が減るので、以上を繰り返すことで目的の最小有向全域木を発見することができます。繰り返すといっても、縮約した状態で入次数が \(0\) なのは \(r\) と縮約した頂点だけなので、それらについて入る辺のうち最もコストの小さい辺を選べば良いです。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
template<class T> void chmin(T& a, T b){ if(a > b) a = b; }
template<class T> void chmax(T& a, T b){ if(a < b) a = b; }


int main(){
    ll N;
    cin >> N;
    vector<array<ll, 3>> trampolines(N);
    for(auto& t : trampolines) for(ll& x : t) cin >> x;
    vector A(N, vector<ll>(N, INF));
    // A[i][j] := (j -> i のコスト) を計算
    for(ll i = 0; i < N; i++){
        auto [x1, y1, P_] = trampolines[i];
        for(ll j = 0; j < N; j++) if(i != j){
            auto [x2, y2, P] = trampolines[j];
            A[i][j] = (abs(x1 - x2) + abs(y1 - y2) + P - 1) / P;
        }
    }
    ll ans = 0;
    vector<ll> parent(N); // 有向森における親 (親がないなら i)
    for(ll i = 0; i < N; i++) parent[i] = i;
    // 頂点 i に入る最もコストの小さい辺
    auto get_min = [&](ll i){
        ll j = min_element(A[i].begin(), A[i].end()) - A[i].begin();
        return array{j, i, A[i][j]}; // {from, to, cost}
    };
    function<void(ll)> add_edge;
    // サイクルを 1 頂点に圧縮する
    function<void(vector<bool>)> compress = [&](vector<bool> cycle){
        vector<ll> idx;
        for(ll i = 0; i < N; i++) if(cycle[i]) idx.push_back(i);
        assert(idx.size() >= 2);
        const ll leader = idx[0];
        for(ll& p : parent) if(cycle[p]) p = leader;
        for(ll i : idx) for(ll j : idx) A[i][j] = INF;
        for(int i = 0; i < N; i++) if(!cycle[i]){
            ll mn1 = INF, mn2 = INF;
            for(ll j : idx){
                chmin(mn1, A[i][j]);
                chmin(mn2, A[j][i]);
                A[i][j] = A[j][i] = INF;
            }
            A[i][leader] = mn1;
            A[leader][i] = mn2;
        }
        // 圧縮した頂点に入る辺がなくなるので追加
        add_edge(leader);
    };
    // 頂点 i に入る辺を有向森に追加する
    add_edge = [&](ll i){
        // まだ頂点 i に入る辺がない <=> 有向森の根の 1 つ
        assert(parent[i] == i);
        // コストの最も大きい辺 1 つを保留
        static auto mx_edge = get_min(0);
        auto edge = get_min(i);
        if(mx_edge[2] < edge[2]) swap(mx_edge, edge);
        
        auto [from, to, cost] = edge;
        chmax(ans, cost);
        parent[to] = from;
        // サイクル検出 (to が根であったのでサイクルになるなら辺 from - to を含む)
        vector<bool> cycle(N);
        cycle[from] = cycle[to] = true;
        ll at = parent[from];
        while(!cycle[at]){
            cycle[at] = true;
            at = parent[at];
        }
        // サイクルができたら 1 頂点に圧縮 (有向森であることが保たれる)
        if(at == to) compress(move(cycle));
    };
    // 全ての頂点について、入る辺で最も最もコストの小さい辺を追加する (i = 0 は保留済み)
    for(int i = 1; i < N; i++) add_edge(i);
    // (頂点数) - (辺数) = 1 で、サイクルのない有向森ができる。これは有向全域木
    cout << ans << endl;
}