显示代码纯文本
#include<bits/stdc++.h>
#define QWQ cout<<"qwq";
using namespace std;
const int maxn=10005;
const int inf=1500000000;
int f[maxn*100];
struct cow{int l,r,sum;}a[maxn];
bool cmp(cow a,cow b){return a.r<b.r;}
struct tree_{int sum;}tree[50*maxn];
void pushup(int root){
tree[root].sum=min(tree[root<<1].sum,
tree[root<<1|1].sum);}
void build(int root,int l,int r){
tree[root].sum=inf;
if(l==r)return ;
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);}
void add(int root,int l,int r,int x,int y){
if(l==r){tree[root].sum=y;return ;}
int mid=(l+r)>>1;
if(x<=mid)add(root<<1,l,mid,x,y);
else add(root<<1|1,mid+1,r,x,y);
pushup(root);}
int ask(int root,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr)return tree[root].sum;
int mid=(l+r)>>1;
int ans=1<<30;
if(ql<=mid)ans=min(ans,ask(root<<1,l,mid,ql,qr));
if(qr>mid)ans=min(ans,ask(root<<1|1,mid+1,r,ql,qr));
return ans;}
int main(){
freopen("clean.in","r",stdin);
freopen("clean.out","w",stdout);
int n,q,w;
cin>>n>>q>>w;
for(int i=1;i<=w;i++)f[i]=inf;
f[q]=0;
for(int i=1;i<=n;i++)
cin>>a[i].l>>a[i].r>>a[i].sum;
sort(a+1,a+1+n,cmp);
build(1,q,w);
add(1,q,w,q,0);
for(int i=1;i<=n;i++){
f[a[i].r]=min(f[a[i].r],
ask(1,q,w,a[i].l-1,a[i].r)+a[i].sum);
add(1,q,w,a[i].r,f[a[i].r]);}
if(f[a[n].r]==inf)cout<<-1;
else cout<<f[a[n].r];
return 0;
}