动态规划，plate[i]中leftpath为左端到地面最短距离,rightpath为右端到地面最短距离


#include <iostream>
using namespace std;

const int MAX=1200;
const int PATHLIMIT=100000000;
struct p
{
	int x1,x2,h;
	int leftPath,rightpath;
}plate[MAX];
 
int cmp(const void *a,const void *b)
{
	return( (*(struct p*)b).h-(*(struct p*)a).h);
}

void main()
{
	int t;
	cin>>t;

	int num,x,y,max;
	int i,j;
		

	while(t--)
	{
		//输入和初始化
		cin>>num>>x>>y>>max;
		for(i=0;i<num;i++){
			cin>>plate[i].x1>>plate[i].x2>>plate[i].h;
			plate[i].leftPath=PATHLIMIT;
			plate[i].rightpath=PATHLIMIT;
		}

		//排序
		qsort(plate,num,sizeof(struct p),cmp);
		//地面为第num+1个平台	
		plate[num].x1=-20000,	plate[num].x2=20000;
		plate[num].h=0;
		plate[num].leftPath=0,	plate[num].rightpath=0;

		//统计从每个平台的左右两边到达地面的最短路径，不能到达的路径长超过PATHLIMIT
		for(i=num-1;i>=0;i--)
		{
			for(j=i+1;j<=num;j++)
			{
				if(plate[i].h-plate[j].h<=max && plate[i].x1>=plate[j].x1 && plate[i].x1<=plate[j].x2)
				{
					int left1,left2;
					left1=(plate[i].h-plate[j].h)+(plate[i].x1-plate[j].x1)+plate[j].leftPath;
					left2=(plate[i].h-plate[j].h)+(plate[j].x2-plate[i].x1)+plate[j].rightpath;
					if(j==num) {
						left1=plate[i].h;
						left2=plate[i].h;
					}
					if(left1<left2) plate[i].leftPath=left1;
					else			plate[i].leftPath=left2;
					break;
				}
			}
			for(j=i+1;j<=num;j++)
			{
				if(plate[i].h-plate[j].h<=max && plate[i].x2>=plate[j].x1 && plate[i].x2<=plate[j].x2)
				{
					int right1,right2;
					right1=(plate[i].h-plate[j].h)+(plate[i].x2-plate[j].x1)+plate[j].leftPath;
					right2=(plate[i].h-plate[j].h)+(plate[j].x2-plate[i].x2)+plate[j].rightpath;
					if(j==num) {
						right1=plate[i].h;
						right2=plate[i].h;
					}
					if(right1<right2) plate[i].rightpath=right1;
					else			  plate[i].rightpath=right2;
					break;
				}
			}
		}

		//判断结果
		for(i=0;i<num;i++)
			if(y-plate[i].h<=max && x>=plate[i].x1 && x<=plate[i].x2)
				break;
		

	

		int shortest=(y-plate[i].h)+(x-plate[i].x1)+plate[i].leftPath; //leftpath
		int temp=(y-plate[i].h)+(plate[i].x2-x)+plate[i].rightpath;    //rightpath
		
		if(shortest>temp) shortest=temp;

		cout<<shortest<<endl;
	}
}