题目大意：给定一些点之间的位置关系，求两个点之间的曼哈顿距离

此题土豪题。只是POJ也有一道相同的题，能够刷一下

别被题目坑到了，这题不强制在线。把询问离线处理就可以

然后就是带权并查集的问题了。。

。

将权值设为方向向量，重载+和-，依照正常权值并查集做即可了

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 40400

using namespace std;

struct abcd{

	int x,y;

	abcd(){}

	abcd(int X,int Y):x(X),y(Y){}

	abcd operator + (const abcd &Y) const

	{

		return abcd( x+Y.x , y+Y.y );

	}

	abcd operator - (const abcd &Y) const

	{

		return abcd( x-Y.x , y-Y.y );

	}

}f[M];

struct operation{

	int x,y;

	abcd temp;

}operations[M];

struct query{

	int x,y,z,pos;

	bool operator < (const query &Y) const

	{

		return z < Y.z ;

	}

}queries[10100];

int n,m,q,fa[M],ans[10100];

int Distance(abcd x)

{

	return abs(x.x)+abs(x.y);

}

int Find(int x)

{

	if(!fa[x]||fa[x]==x)

		return fa[x]=x;

	int y=fa[x];

	fa[x]=Find(fa[x]);

	f[x]=f[y]+f[x];

	return fa[x];

}

int main()

{

	int i,j,x,y,z;

	char p[10];

	cin>>n>>m;

	for(i=1;i<=m;i++)

	{

		scanf("%d%d%d%s",&operations[i].x,&operations[i].y,&z,p);

		switch(p[0])

		{

			case 'E':operations[i].temp=abcd(z,0);break;

			case 'W':operations[i].temp=abcd(-z,0);break;

			case 'N':operations[i].temp=abcd(0,z);break;

			case 'S':operations[i].temp=abcd(0,-z);break;

		}

	}

	cin>>q;

	for(i=1;i<=q;i++)

		scanf("%d%d%d",&queries[i].x,&queries[i].y,&queries[i].z),queries[i].pos=i;

	sort(queries+1,queries+q+1);

	for(i=1,j=1;i<=q;i++)

	{

		for(;j<=queries[i].z;j++)

		{

			int x=operations[j].x;

			int y=operations[j].y;

			int fx=Find(x),fy=Find(y);

			fa[fy]=fx;

			f[fy]=f[x]-f[y]+operations[j].temp;

		}

		int x=queries[i].x;

		int y=queries[i].y;

		if( Find(x)!=Find(y) )

			ans[queries[i].pos]=-1;

		else

			ans[queries[i].pos]=Distance(f[x]-f[y]);

	}

	for(i=1;i<=q;i++)

		printf("%d\n",ans[i]);

}