POJ 1661 Help Jimmy

时间:2021-06-24 08:46:16
/*96655 's source code for M
Memory: 8604 KB Time: 63 MS
Language: G++ Result: Accepted
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
short x[],y[],h[];
short xx[],hh[],xcnt,hcnt,d,ww,f;
int dp[][];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,bb,cc,m;
scanf("%d%d%d%d",&n,&bb,&cc,&m);
xcnt=hcnt=;
for(int i=; i<=n; ++i)
{
scanf("%d%d%d",&x[i],&y[i],&h[i]);
xx[xcnt++]=x[i];
xx[xcnt++]=y[i];
hh[hcnt++]=h[i];
}
xx[xcnt++]=bb;
hh[hcnt++]=;
sort(xx,xx+xcnt);
sort(hh,hh+hcnt,cmp);
d=;
for(int i=; i<xcnt; i++)
if(xx[i]!=xx[i-])xx[d++]=xx[i];
xcnt=d,d=;
for(int i=; i<hcnt; i++)
if(hh[i]!=hh[i-])hh[d++]=hh[i];
hcnt=d;
vector<int>a[hcnt+];
memset(dp,-,sizeof(dp));
int ans=0x3f3f3f3f;
for(int i=; i<xcnt; i++)
dp[hcnt-][i]=ans;
for(int i=; i<=n; i++)
{
int id;
for(int j=; j<hcnt; j++)
if(h[i]==hh[j])
{
id=j;
break;
}
int s=lower_bound(xx,xx+xcnt,x[i])-xx;
int t=lower_bound(xx,xx+xcnt,y[i])-xx;
a[id].push_back(s);
a[id].push_back(t);
for(int j=s; j<=t; ++j)
dp[id][j]=ans;
}
f=lower_bound(xx,xx+xcnt,bb)-xx;
for(int i=; i<hcnt; i++)
{
if(dp[i][f]!=-)
{
dp[i][f]=cc-hh[i];
ww=i;
break;
}
}
for(int i=ww; i<hcnt-; ++i)
{
for(int j=; j<xcnt; j++)
{
if(dp[i][j]<ans&&dp[i][j]!=-)
{
int s,t;
for(int k=;k<a[i].size();k+=)
{
if(a[i][k-]<=j&&a[i][k]>=j)
{
s=a[i][k-];
t=a[i][k];
break;
}
}
int l=xx[j]-xx[s],r=xx[t]-xx[j];
dp[i][s]=min(dp[i][s],dp[i][j]+l);
dp[i][t]=min(dp[i][t],dp[i][j]+r); }
}
for(int j=; j<a[i].size(); ++j)
{
int p=a[i][j];
if(dp[i][p]!=-&&dp[i][p]<ans)
{
for(int k=i+; k<hcnt&&hh[i]-hh[k]<=m; k++)
if(dp[k][p]!=-)
{
dp[k][p]=min(dp[k][p],dp[i][p]+hh[i]-hh[k]);
break;
}
}
}
}
for(int i=; i<xcnt; i++)
ans=min(ans,dp[hcnt-][i]);
printf("%d\n",ans);
}
return ;
}