POJ 1661 Help Jimmy 최단거리

제목 대의: POJ에서 보기 드문 중국어 문제입니다. 직접 보세요. 제목의 뜻은 매우 간단합니다.
사고방식: 이 책은 DP의 문제인데 내가 가장 짧은 물로 지나갔는데 0ms가 될 줄은 몰랐다.
그림을 짓는 사고방식은 비교적 간단하지만 실현하기가 비교적 어렵다.모든 물건을 높이에 따라 순서를 정하고 위에서 아래로 n^2까지 좌우 단점을 매거한 다음에 조건을 만족시키는 연변은 고도차+수평거리차이다.
SPFA 뛰면 돼.Jimmy가 직접 지면으로 뛰어내릴 수 있는 상황을 주의해라. 이것은 한 번 흔들렸다.
CODE:

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 200010
using namespace std;

struct Complex{
	int l,r;
	bool _l,_r;
	int height;

	Complex(int _,int __,int ___):l(_),r(__),height(___) {}
	Complex() {}
	bool operator <(const Complex &a)const {
		return height > a.height;
	}
	void Read() {
		scanf("%d%d%d",&l,&r,&height);
		_l = _r = false;
	}
}point[MAX];

int cases;
int points,x,y,limit;
int head[MAX],total;
int next[MAX],aim[MAX],length[MAX];

int f[MAX];
bool v[MAX];

inline void Initialize();
inline void Add(int x,int y,int len);
inline void SPFA(int start);

int main()
{
	for(cin >> cases;cases; --cases) {
		scanf("%d%d%d%d",&points,&x,&y,&limit);
		Initialize();
		for(int i = 1;i <= points; ++i)
			point[i].Read();
		point[++points] = Complex(-20000,20000,0);
		point[0].height = y;
		sort(point + 1,point + points + 1);
		for(int i = 1;i <= points; ++i)
			if(x >= point[i].l && x <= point[i].r)
				if(y - point[i].height <= limit) {
					Add(1,i << 1,y - point[i].height + x - point[i].l);
					Add(1,i << 1|1,y - point[i].height + point[i].r - x);
					break;
				}
		for(int i = 1;i <= points; ++i)
			for(int j = 1;j < i; ++j) {
				if(point[j].height - point[i].height > limit)	continue;
				if(!point[j]._l && point[j].l >= point[i].l && point[j].l <= point[i].r) {
					Add(j << 1,i << 1,point[j].height - point[i].height + point[j].l - point[i].l);
					Add(j << 1,i << 1|1,point[j].height - point[i].height + point[i].r - point[j].l);
					point[j]._l = true;
				}
				if(!point[j]._r && point[j].r >= point[i].l && point[j].r <= point[i].r) {
					Add(j << 1|1,i << 1,point[j].height - point[i].height + point[j].r - point[i].l);
					Add(j << 1|1,i << 1|1,point[j].height - point[i].height + point[i].r - point[j].r);
					point[j]._r = true;
				}
			}
		SPFA(1);
		printf("%d
",f[points << 1]);
	}
	return 0;
}

inline void Initialize()
{
	total = 0;
	memset(head,0,sizeof(head));
}

inline void Add(int x,int y,int len)
{
	next[++total] = head[x];
	aim[total] = y;
	if(y == (points << 1) || y == (points << 1|1))
		length[total] = point[x >> 1].height;
	else	length[total] = len;
	head[x] = total;
}

inline void SPFA(int start)
{
	static queue<int> q;
	while(!q.empty())	q.pop();
	memset(f,0x3f,sizeof(f));
	f[start] = 0;
	q.push(start);
	while(!q.empty()) {
		int x = q.front(); q.pop();
		v[x] = false;
		for(int i = head[x];i;i = next[i]) 
			if(f[aim[i]] > f[x] + length[i]) {
				f[aim[i]] = f[x] + length[i];
				if(!v[aim[i]]) {
					v[aim[i]] = true;
					q.push(aim[i]);
				}
			}
	}
}