60求调
查看原帖
60求调
938645
zhaodexuan20121211楼主2024/12/2 19:51
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+5;
ll n,dp[N][5],s,t,ans=INT_MAX;
struct Strict
{
	ll h,l,r,id;
	bool operator <(const Strict & o)const
	{
		return h>o.h;
	}
}a[N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		dp[i][1] = INT_MAX;
		dp[i][0] = INT_MAX;
	}
	cin>>s>>t;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].l>>a[i].r>>a[i].h;
		a[i].id = i;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		if(a[i].id==t)
		{
			t = i;
			break;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i].id==s)
		{
			s = i;
			break;
		}
	}
	if(s>t)
	{
		cout<<-1;
		return 0;
	}
	if(s==t)
	{
		cout<<0;
		return 0;
	}
	queue<ll>q0,q1;
	dp[s][0] = 0;
	dp[s][1] = a[s].r-a[s].l;
	q0.push(s);
	q1.push(s);
	while(q0.size()||q1.size())
	{
		if(q0.size())
		{
			ll f=q0.front();
			q0.pop();
			for(int i=f+1;i<t;i++)
			{
				if(a[i].l<=a[f].l&&a[i].r>=a[f].l)
				{
					if(dp[i][0]>dp[f][0]+a[f].h-a[i].h+a[f].l-a[i].l)
					{
						dp[i][0] = dp[f][0]+a[f].h-a[i].h+a[f].l-a[i].l;
						q0.push(i);
					}
					if(dp[i][1]>dp[f][0]+a[f].h-a[i].h+a[i].r-a[f].l)
					{
						dp[i][1] = dp[f][0]+a[f].h-a[i].h+a[i].r-a[f].l;
						q1.push(i);
					}
				}
			}
			if(a[t].l<=a[f].l&&a[t].r>=a[f].l)
			{
				ans = min(ans,dp[f][0]+a[f].h-a[t].h);
			}
		}
		if(q1.size())
		{
			ll f=q1.front();
			q1.pop();
			for(int i=f+1;i<t;i++)
			{
				if(a[i].l<=a[f].r&&a[i].r>=a[f].r)
				{
					if(dp[i][0]>dp[f][1]+a[f].h-a[i].h+a[f].r-a[i].l)
					{
						dp[i][0] = dp[f][1]+a[f].h-a[i].h+a[f].r-a[i].l;
						q0.push(i);
					}
					if(dp[i][1]>dp[f][1]+a[f].h-a[i].h+a[i].r-a[f].r)
					{
						dp[i][1] = dp[f][1]+a[f].h-a[i].h+a[i].r-a[f].r;
						q1.push(i);
					}
				}
			}
			if(a[t].l<=a[f].r&&a[t].r>=a[f].r)
			{
				ans = min(ans,dp[f][1]+a[f].h-a[t].h);
			}
		}
	}
	if(ans==INT_MAX)
	{
		cout<<-1;
	}
	else
	{
		cout<<ans;
	}
    return 0;
}

玄关

2024/12/2 19:51
加载中...