poj1661——Help Jimmy//最短路

思路：转化为求最短路。建图比较麻烦，每一个平台拆成两个点，上下两个平台之间距离不超过maxlen的点加边。

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
#define maxn 2100
#define maxcost 99999999
int maxlen,sx,sh,n,st,ed;
class node
{
public:
	int lx,rx,h;
};
node p[1005];
class map
{
public :
	int to,len;
	int next;
};
map g[10000];
int head[2100],cnt;
bool cmp(node &a,node &b)
{
	if(a.h >b.h )return true;
	return false;
};
void add(int u,int v,int len)
{
	g[++cnt].to =v;
	g[cnt].len =len;
	g[cnt].next=head[u];
	head[u]=cnt;
}
void build()//建图
{
	int i,j;
	for(i=0;i<n;i++)
	{
		bool l=false,r=false;
		j=i+1;
		while((l==false||r==false)&&p[i].h -p[j].h <=maxlen&&j<n)
		{
			if(p[j].lx <=p[i].lx &&p[j].rx >=p[i].lx &&l==false)
			{
				l =true;
				add(2*i,2*j,p[i].lx -p[j].lx );
				add(2*i,2*j+1,p[j].rx -p[i].lx );
			}
			if(p[j].lx <=p[i].rx &&p[j].rx >=p[i].rx &&r==false)
			{
				r=true;
				add(2*i+1,2*j,p[i].rx -p[j].lx );
				add(2*i+1,2*j+1,p[j].rx -p[i].rx );
			}
			j++;
		}
		if(p[i].h <=maxlen)
		{
			if(l==false) add(2*i,ed,0);
			if(r==false) add(2*i+1,ed,0);
		}
	}
}
int vis[maxn],dist[maxn],par[maxn];
int dij()
{
	int i,min,k,j,dis,v;
	for(i=0;i<=ed;i++)
	{
		vis[i]=0;
		par[i]=0;
		dist[i]=maxcost;
	}
	for(i=head[st];i;i=g[i].next )
	{
		v=g[i].to ;
		dist[v]=g[i].len ;
	}
	vis[st]=1;dist[st]=0;
	for(i=0;i<=ed;i++)
	{
		min=maxcost;k=st;
		for(j=0;j<=ed;j++)
			if(dist[j]<min&&vis[j]==0)
			{
				min=dist[j];
				k=j;
			}
			vis[k]=1;
			for(j=head[k];j;j=g[j].next )
			{
				v=g[j].to ;
				dis=dist[k]+g[j].len ;
				if(vis[v]==0&&dist[v]>dis)
				{
					dist[v]=dis;
					par[v]=k;
				}
			}
	}
	return dist[ed];
}
int main()
{
	int test,i;
	cin>>test;
	while(test--)
	{
		cin>>n>>sx>>sh>>maxlen;
		for(i=0;i<n;i++)
		{
			scanf("%d%d%d",&p[i].lx,&p[i].rx,&p[i].h);
		}
		sort(p,p+n,cmp);
		memset(head,0,sizeof(head));
		cnt=0;
		i=0;
		st=2*n+2;
		ed=2*n+3;
		while(i<n)
		{
			if(p[i].lx <=sx&&p[i].rx >=sx)
			{
				add(st,2*i,sx-p[i].lx );
				add(st,2*i+1,p[i].rx -sx);
				break;
			}
			i++;
		}
		if(i==n)
			printf("%d\n",sh);
		else 
		{
			build();
			printf("%d\n",dij()+sh);
		}
	}
	return 0;
}