Submission #4299147

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,P> PP;
const ll INF = (1LL<<60);
const ll MAX_N = 100005;


struct data{
  map<ll,ll> dat[MAX_N];

  void SetValue(ll a,ll b,ll val){

    ll cb=b;
    while(a<MAX_N){
      b=cb;
      while(b<MAX_N){
        if( dat[a].count(b) == 0 )dat[a][b]=INF;
        dat[a][b]=min(dat[a][b],val);
        b+=(b&-b);
      }
      a+=(a&-a);
    }
  }
  
  ll GetMin(ll a,ll b){
    ll cb=b;
    ll res=INF;
    while(a){
      b=cb;
      while(b){
        if( dat[a].count(b) == 0 )dat[a][b]=INF;
        res=min(res,dat[a][b]);
        b-=(b&-b);
      }
      a-=(a&-a);
    }
    return res;
  }
};

data tree;
int N, si,ti;
vector<PP> t;
ll X[100005],Y[100005],C[100005], ID[100005];
ll dp[100005];

void solve(){
  int sj;
  int tj;
  for(int i=0;i<N;i++){
    if( ID[i] == si )sj = i;
    if( ID[i] == ti )tj = i;
    //    cout<<X[i]<<' '<<Y[i]<<endl;
  }

  tree.SetValue( X[ sj ] , Y[ sj ] , C[ sj ] );
  
  for(int i=sj;i<N;i++){
    
    ll ans=tree.GetMin(X[i],Y[i]);
    //    cout<<i<<' '<<ans<<' '<<N<<endl;
    
    if( i == tj ){
      cout<<ans<<endl;
      return;
    }
    dp[i]=ans;
    tree.SetValue(X[i],Y[i],ans+C[i]);
  }
}

int main(){
  cin>>N>>si>>ti;
  for(int i=0;i<N;i++){
    cin>>X[i]>>Y[i]>>C[i];
    t.push_back(PP(P(X[i],Y[i]),P(C[i],i)));
  }

  
  si--;
  ti--;
  sort(t.begin(),t.end());
  for(int i=0;i<N;i++){
    X[i]=t[i].first.first;
    Y[i]=t[i].first.second;
    C[i]=t[i].second.first;
    ID[i]=t[i].second.second;
  }
  
  vector<ll> tmp;
  for(int i=0;i<N;i++){
    tmp.push_back(X[i]);  
  }
  sort(tmp.begin(),tmp.end());
  tmp.erase( unique( tmp.begin(), tmp.end()) , tmp.end() );
  for(int i=0;i<N;i++){
    X[i]=lower_bound( tmp.begin(), tmp.end(), X[i]) - tmp.begin()+1;
  }

  tmp.clear();
  for(int i=0;i<N;i++){
    tmp.push_back(Y[i]);  
  }
  sort(tmp.begin(),tmp.end());
  tmp.erase( unique( tmp.begin(), tmp.end()) , tmp.end() );
  for(int i=0;i<N;i++){
    Y[i]=lower_bound( tmp.begin(), tmp.end(), Y[i]) - tmp.begin()+1;
  }

  solve();
  return 0;
}

Submission Info

Judge Result