二分探索の上限をinfにするのは危険 D - Jumping Takahashi 2

• 問題 https://atcoder.jp/contests/abc257/tasks/abc257_d
• 方針 Sを二分探索する。始点は全探索し、そこから全ての点を訪問できるかBFSで判定する
• 落とし穴があった。提出したWAのコードはこちら https://atcoder.jp/contests/abc257/submissions/48522778

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;
    cin>>N;
    
    VI X(N);
    VI Y(N);
    VI P(N);
    rep(i,N){
      cin>>X[i]>>Y[i]>>P[i];
    }

    auto L1 = [&](ll i, ll j){
      return abs(X[i]-X[j]) + abs(Y[i]-Y[j]);
    };

    auto f = [&](ll start, ll S){
      queue<ll> q; q.push(start);
      set<ll> not_visited;
      rep(i,N){
        if(i!=start)not_visited.insert(i);
      }
      while(q.size()){
        ll a = q.front(); q.pop();
        VI del_list;
        for(ll to : not_visited){
          if(P[a]*S >= L1(a,to)){ // ★
            q.push(to);
            del_list.push_back(to);
          }
        }
        for(ll idx : del_list){
          not_visited.erase(idx);
        }
      }
      return SZ(not_visited)==0;
    };

    ll left=0; // can't
    ll right=1e15; // can
    while(right-left>1){
      ll center=(right+left)/2;

      bool can=false;
      rep(i,N){
        if(can)break;
        bool result = f(i,center);
        if(result){
          can=true;
        }
      }

      if(can){
        right=center;
      }else{
        left=center;
      }
    }
    p(right);

    return 0;
}

• 雑にleft=0, right=1e15としていたが、辺を張れるかの判定条件（★の箇所）でoverflowしていた
• 入力の値域から、right=4*1e9で十分なので、そう変更すればACする

Holes (English Edition)