BZOJ 3362 POJ 1984 Navigation Nightmare 并与正确集中检查

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

struct Complex{
	int x,y,len;
	char c;
}edge[MAX];
struct Ask{
	int x,y;
	int pos,_id;
	bool operator <(const Ask &a)const {
		return pos < a.pos;
	}
}ask[MAX];
struct Status{
	int x,y;

	Status(int _,int __):x(_),y(__) {}
	Status() {}
	Status operator +(const Status &a)const {
		return Status(x + a.x,y + a.y);
	}
	Status operator -(const Status &a)const {
		return Status(x - a.x,y - a.y);
	}
}f[MAX];

int points,edges,asks;
int father[MAX];
int ans[MAX];

char s[10];

void Pretreatment();

int Find(int x);

int main()
{
	cin >> points >> edges;
	Pretreatment();
	for(int i = 1;i <= edges; ++i) {
		scanf("%d%d%d%s",&edge[i].x,&edge[i].y,&edge[i].len,s);
		edge[i].c = s[0];
	}
	cin >> asks;
	for(int i = 1;i <= asks; ++i)
		scanf("%d%d%d",&ask[i].x,&ask[i].y,&ask[i].pos),ask[i]._id = i;
	sort(ask + 1,ask + asks + 1);
	int now = 1;
	for(int i = 1;i <= edges; ++i) {
		int fx = Find(edge[i].x);
		int fy = Find(edge[i].y);
		if(fx != fy) {
			father[fy] = fx;
			Status temp;
			if(edge[i].c == 'N')	temp = Status(0,edge[i].len);
			if(edge[i].c == 'S')	temp = Status(0,-edge[i].len);
			if(edge[i].c == 'E')	temp = Status(edge[i].len,0);
			if(edge[i].c == 'W')	temp = Status(-edge[i].len,0);
			f[fy] = f[edge[i].x] - f[edge[i].y] + temp;
		}
		while(i >= ask[now].pos && now <= asks) {
			int fx = Find(ask[now].x);
			int fy = Find(ask[now].y);
			if(fx != fy)	ans[ask[now]._id] = -1;
			else {
				Status temp = f[ask[now].x] - f[ask[now].y];
				ans[ask[now]._id] = abs(temp.x) + abs(temp.y);
			}
			++now;
		}
	}
	for(int i = 1;i <= asks; ++i)
		printf("%d\n",ans[i]);
	return 0;
}

void Pretreatment()
{
	for(int i = 1;i <= points; ++i)
		father[i] = i;
}

int Find(int x)
{
	if(father[x] == x)	return x;
	int temp = father[x];
	father[x] = Find(father[x]);
	f[x] = f[x] + f[temp];
	return father[x];
}