求助
查看原帖
求助
563069
UQAQU楼主2024/9/1 16:51
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const int N=1e6+7;
struct bz{
	ll l,r,h,bj;
}db[2007];
ll dp[2007][10];
bool cmp(bz a,bz b){
	if (a.h==b.h){
		if (a.l==b.l){
			return a.r>b.r;
		}
		return a.l<b.l;
	}
	return a.h>b.h;
}
int main()
{
	int n,s,t;
	cin>>n>>s>>t;
	int hs,ht;
	for (int i=1;i<=n;i++){
		cin>>db[i].l>>db[i].r>>db[i].h;
		db[i].bj=i,dp[i][0]=0x3f3f3f,dp[i][1]=0x3f3f3f;
	}
	sort(db+1,db+1+n,cmp);
	int s1,t1;
	for (int i=1;i<=n;i++){
		if (db[i].bj==s){
			s1=i;
		}
		if (db[i].bj==t){
			t1=i;
		}
	}
	if (db[s1].h<db[t1].h){
		cout<<-1<<endl;
		return 0;
	}
	dp[s1][0]=0,dp[s1][1]=db[s1].r-db[s1].l;
	ll ans=0x3f3f3f;
	for (int i=s1;i<=t1;i++){
		for (int j=i+1;j<=t1;j++){
			if (db[i].l<=db[j].r && db[i].l>=db[j].l && db[i].h>db[j].h){
				ll gd=db[i].h-db[j].h;
				dp[j][0]=min(dp[j][0],dp[i][0]+gd+db[i].l-db[j].l);
				dp[j][1]=min(dp[j][1],dp[i][0]+gd+db[j].r-db[i].l);
				if (j==t1){
					ans=min(ans,dp[i][0]+gd);
				}
                break;
			}
		}
		for (int j=i+1;j<=t1;j++){
			if (db[j].l<=db[i].r && db[j].r>=db[i].r && db[i].h>db[j].h){
				ll gd=db[i].h-db[j].h;
				dp[j][0]=min(dp[j][1],dp[i][1]+gd+db[i].r-db[j].l);
				dp[j][1]=min(dp[j][1],dp[i][1]+gd+db[j].r-db[i].r);
				if (j==t1){
					ans=min(ans,dp[i][1]+gd);
				}
                break;
			}
		}
	}
	if (ans==0x3f3f3f){
		cout<<-1<<endl;
	}
	else{
		cout<<ans<<endl;
	}
	return 0;
}
2024/9/1 16:51
加载中...