#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;

const ll INF=1e18;
const int N=100005;
int n,m,cnt,nn;
struct po{
    int l,r,v;
};
po a[N];
int X[N<<1];
struct node{
    ll mn;
};
node t[N<<2];

int cmp(const po &A,const po &B) {return A.r<B.r;}

void build(int bh,int l,int r)
{
    if (l!=1) t[bh].mn=INF;
    else t[bh].mn=0;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(bh<<1,l,mid);
    build(bh<<1|1,mid+1,r);
}

void insert(int bh,int l,int r,int x,ll z)
{
    if (l==r)
    {
        t[bh].mn=min(t[bh].mn,z);
        return;
    }
    int mid=(l+r)>>1;
    if (x<=mid) insert(bh<<1,l,mid,x,z);
    else insert(bh<<1|1,mid+1,r,x,z);
    t[bh].mn=min(t[bh<<1].mn,t[bh<<1|1].mn);
}

ll ask(int bh,int l,int r,int L,int R)
{
    if (l>=L&&r<=R) return t[bh].mn;
    ll ans=INF;
    int mid=(l+r)>>1;
    if (L<=mid) ans=min(ans,ask(bh<<1,l,mid,L,R));
    if (R>mid) ans=min(ans,ask(bh<<1|1,mid+1,r,L,R));
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    for (int cas=1;cas<=T;cas++)
    {
        scanf("%d%d",&n,&m);
        cnt=0; nn=0;
        for (int i=1;i<=n;i++) 
        {
            cnt++;
            scanf("%d%d%d",&a[i].r,&a[i].l,&a[i].v);
            if (a[i].l>a[i].r) cnt--;
            else X[++nn]=a[i].r;
        }

        X[++nn]=1;                            //dp初始值 
        sort(X+1,X+1+nn);
        nn=unique(X+1,X+1+nn)-X-1;
        build(1,1,nn);

        sort(a+1,a+1+cnt,cmp);
        for (int i=1;i<=cnt;i++)
        {
            int x=lower_bound(X+1,X+1+nn,a[i].l)-X;
            int y=lower_bound(X+1,X+1+nn,a[i].r)-X;
            ll minn=ask(1,1,nn,x,y);
            if (minn!=INF)
                insert(1,1,nn,y,minn+(ll)a[i].v);
        }

        printf("Case #%d: ",cas);
        ll ans=ask(1,1,nn,lower_bound(X+1,X+1+nn,m)-X,nn);
        if (ans!=INF) printf("%d\n",ans);
        else printf("-1\n");
    } 
    return 0;
}

对于这个题目, 因为要离散化, 所以有些c++选手会使用stl, 这会让程序变得非常慢. 希望慎用.

解答: http://pan.baidu.com/s/1ntJW1jr