TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

Jumping Takahashi 2

問題

D – Jumping Takahashi 2
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
// using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

int N;
vector<ll> x;
vector<ll> y;
vector<ll> P;

bool f(ll mid) {
  vector<vector<int>> canVisit(N, vector<int>(N, 0));
  rep(i, N) {
    rep(j, N) {
      ll dist = abs(x[i] - x[j]) + abs(y[i] - y[j]);
      if (dist <= P[i] * mid) {
        canVisit[i][j] = 1;
      }
    }
  }

  rep(k, N) {
    rep(i, N) {
      rep(j, N) {
        // if (canVisit[k][j] && canVisit[i][k]) {
        //   canVisit[i][j] = true;
        // }
        canVisit[i][j] |= canVisit[k][j] & canVisit[i][k];
      }
    }
  }

  rep(i, N) {
    bool flg = true;
    rep(j, N){
      if(canVisit[i][j] == 0) {
        flg = false;
      }
    }
    if(flg) {
      return true;
    }
  }

  return false;
}

int main() {
  cin >> N;
  
  x.resize(N);
  y.resize(N);
  P.resize(N);
  rep(i, N) {
    cin >> x[i] >> y[i] >> P[i];
  }

  ll wa = 0;
  ll ac = 4000000000LL;
  while(1 < ac - wa) {
    ll mid = (ac + wa) / 2;
    if (f(mid)) {
      ac = mid;
    } else {
      wa = mid;
    }
  }

  cout << ac << endl;
  return 0;
}