最近水两道acm的题，发现好久不写题，的确不行了，都忘光了。
就是水题也得卡个半死。
祝西电同学们今天网赛发挥出色！
//每个平台看做两个点，左端和右端。
//dp[i][0]，dp[i][1]分别表示从上往下，到第i个平台的左右端点的最短时间。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
int l,r,h;
}t[1010];
int cas,n,X,Y,MAX;
int dp[1010][2];
bool cmp( node a,node b)
{
return a.h>b.h;
}
int main()
{
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d%d%d",&n,&X,&Y,&MAX);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&t[i].l,&t[i].r,&t[i].h);
sort(t+1,t+1+n,cmp);
memset(dp,0x3f,sizeof(dp));
int start=0;
t[0].l=t[0].r=X;
t[0].h=Y;
dp[0][0]=dp[0][1]=0;
for(int i=0;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(t[i].h-t[j].h<=MAX)
{
if(t[i].l>=t[j].l&&t[i].l<=t[j].r)
{
dp[j][0]=min(dp[j][0],dp[i][0]+t[i].l-t[j].l+t[i].h-t[j].h);
dp[j][1]=min(dp[j][1],dp[i][0]+t[j].r-t[i].l+t[i].h-t[j].h);
break;
}
}
}
for(int j=i+1;j<=n;j++)
{
if(t[i].h-t[j].h<=MAX)
{
if(t[i].r>=t[j].l&&t[i].r<=t[j].r)
{
dp[j][0]=min(dp[j][0],dp[i][1]+t[i].r-t[j].l+t[i].h-t[j].h);
dp[j][1]=min(dp[j][1],dp[i][1]+t[j].r-t[i].r+t[i].h-t[j].h);
break;
}
}
}
}
int mi=100000000;
for(int i=n;i>=0;i--)
{
if(t[i].h>MAX)
break;
bool flag=0;
for(int j=i+1;j<=n;j++)
if(t[j].l<=t[i].l&&t[j].r>=t[i].l)
{
flag=1;
break;
}
if(!flag)
mi=min(mi,dp[i][0]+t[i].h);
flag=0;
for(int j=i+1;j<=n;j++)
if(t[j].l<=t[i].r&&t[j].r>=t[i].r)
{
flag=1;
break;
}
if(!flag)
mi=min(mi,dp[i][1]+t[i].h);
}
printf("%d\n",mi);
}
}