信息学奥赛社区

数组已经尽量开小了，挺奇怪的 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=10100,M=87000,INF=0x3f3f3f3f;
int n,st,ed,a[M<<2],ans=INF,dp[M];
struct node
{
	int u,v,w; 
}b[N];
void update(int x,int l,int r,int p,int num)
{
	int mid=(l+r)>>1;
	if(l==r&&l==p)
	{
		a[x]=num;
		return;
	} 
	if(p<=mid) update(x*2,l,mid,p,num);
	else update(x*2+1,mid+1,r,p,num);
	a[x]=min(a[x*2],a[x*2+1]);
}
int query(int x,int l,int r,int ql,int qr)
{
	int mid=(l+r)>>1,mi=INF;
	if(ql<=st) return 0;
	if(ql<=l&&qr>=r) return a[x];
	if(ql<=r) mi=min(mi,query(x*2,l,mid,ql,qr)); 
	if(qr>=l) mi=min(mi,query(x*2+1,mid+1,r,ql,qr));
	return mi;
}
bool cmp(node a1,node a2)
{
	if(a1.u!=a2.u) return a1.u<a2.u;
	return a1.v<a2.v;
}
int main()
{
	scanf("%d%d%d",&n,&st,&ed);
	memset(dp,0x3f,sizeof dp);
	memset(a,0x3f,sizeof a);
	dp[st]=0; 
	update(1,st,ed,st,0);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&b[i].u,&b[i].v,&b[i].w);
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++) 
	{
		dp[b[i].v]=min(dp[b[i].v],query(1,st,ed,b[i].u-1,b[i].v)+b[i].w);
		update(1,st,ed,b[i].v,dp[b[i].v]); 
		if(b[i].v>=ed) ans=min(ans,dp[b[i].v]);
		//printf("%d %lld\n",b[i].v,dp[b[i].v]);
	}
	if(ans>=INF) ans=-1;
	printf("%d",ans);
	return 0;
}