题目是中文的,不解释,但是这道题目的确相当恶心,至少我一开始没有把握它的意思,我的直觉就是,如果一层是[(4,8),(10,8)]的话,那么老鼠一定要走到(5,8)这个坐标才能往下掉,但是呢,题目的意思(我WA后尝试猜测得出的正确题意)就是在(4,8)这个位置就可以往下掉了,我多想了一点点实际生活的逻辑反而不对了。

这道题目是动态规划,先排序,然后从最高一层向下遍历,更新可以到达的下一层的左右端点的最短时间即可。算是简单的动态规划,只是,题意实在恶心。

#include <stdio.h>
#include <stdlib.h>
#define MAXTIME 99999999

int cmp(const void *a,const void *b){
	return *(int*)b-*(int*)a;
}

inline int min(int a,int b){
	if(a<b)return a;return b;
}

int t,N,X,Y,MAX,Floor[1005][5]
/*
0,height;
1,x1;
2,x2;
3,time to x1;
4,time to x2
*/;

int main(){
	int i,j,result;
	scanf("%d",&t);
	while(t--){
		result=MAXTIME;
		scanf("%d%d%d%d",&N,&X,&Y,&MAX);
		for(i=0;i<N;i++){
			scanf("%d%d%d",&Floor[i][1],&Floor[i][2],&Floor[i][0]);
			Floor[i][3]=Floor[i][4]=MAXTIME;
		}
		qsort(Floor,N,sizeof(int[5]),cmp);
		for(i=0;i<N;i++){///第一个台阶,因为总有解,所以不判断是否符合高度
			if(Floor[i][1]<=X&&Floor[i][2]>=X){
				Floor[i][3]=X-Floor[i][1];
				Floor[i][4]=Floor[i][2]-X;
			//	printf("%d %d %dn",i,Floor[i][3],Floor[i][4]);
				break;
			}
		}
		Floor[N][0]=0;
		Floor[N][1]=-MAXTIME;
		Floor[N][2]=MAXTIME;
		Floor[N][3]=MAXTIME;
		Floor[N][4]=MAXTIME;
		for(;i<N;i++){
			if(Floor[i][4]!=MAXTIME){
				for(j=i+1;j<=N;j++){
					if(Floor[i][0]==Floor[j][0])continue;
					if(Floor[j][0]+MAX<Floor[i][0])break;//没有可以下落的层
					if(Floor[j][1]<=Floor[i][1]&&Floor[j][2]>=Floor[i][1]){//左边下落
						if(j==N){
							result=min(result,Floor[i][3]);
							break;
						}
					//	printf("%d %dn",Floor[j][3],Floor[j][4]);
						Floor[j][3]=min(Floor[j][3],Floor[i][3]+Floor[i][1]-Floor[j][1]);//掉到左边
						Floor[j][4]=min(Floor[j][4],Floor[i][3]+Floor[j][2]-Floor[i][1]);//掉到右边
					//	printf("%d left -> %d | %d %dn",i,j,Floor[j][3],Floor[j][4]);
						break;
					}
				}
				for(j=i+1;j<=N;j++){
					if(Floor[i][0]==Floor[j][0])continue;
					if(Floor[j][0]+MAX<Floor[i][0])break;//没有可以下落的层
					if(Floor[j][1]<=Floor[i][2]&&Floor[j][2]>=Floor[i][2]){//右边下落
						if(j==N){
							result=min(result,Floor[i][4]);
							break;
						}
					//	printf("%d %dn",Floor[j][3],Floor[j][4]);
						Floor[j][3]=min(Floor[j][3],Floor[i][4]+Floor[i][2]-Floor[j][1]);//掉到左边
						Floor[j][4]=min(Floor[j][4],Floor[i][4]+Floor[j][2]-Floor[i][2]);//掉到右边
					//	printf("%d right -> %d | %d %dn",i,j,Floor[j][3],Floor[j][4]);
						break;
					}
				}
			}
		}
		if(N==1){
			result=min(Floor[0][3],Floor[0][4]);
		}
		if(result==MAXTIME){
			result=0;
		}
	/*	for(i=0;i<N;i++){
			printf("%d %d %d %d %dn",Floor[i][0],Floor[i][1],Floor[i][2],Floor[i][3],Floor[i][4]);
		}*/
		printf("%dn",result+Y);
	}
	return 0;
}