题目链接：
POJ 1984 Navigation Nightmare
题意：
平面上有n个点，每个点可以在东西南北四个方向上与另外一个点连接，（每个点最多和四个直接连通）
然后有m条语句用以表示这n个点之间的位置关系：a,b,d,S表示a点在b点南方，距离为d（N,W,E分别表示北，西，东）
接着有k条语句来查询：a，b，t：由m条语句中的前t条能否得出a，b两点间的哈夫曼距离，
如果由m条语句中的前t条得出a，b两点不连通，则结果为-1.
分析：
先查询按照查询的t由小到大排序，然后将读入数据读入并查集到相应次序，两个点是否连通可通过find来判断。
x[i]，y[i]分别表示点i到根节点在横向和竖向的距离。
那么如果uu，vv两点连通距离就是abs(x[uu]-x[vv])+abs(y[uu]-y[vv]);
但是输出需要按照查询的顺序输出，所以可以把查询语句用结构体存储，并且结构体中一个变量用于存储查询顺序，
那么计算每条语句的ans时，把查询语句结构体数组按照t排序，输出时，再把查询语句按照查询顺序排序输出。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;const int maxn=40010;
const int maxk=10010;int pre[maxn],x[maxn],y[maxn],n,m,k,a,b,d,tx,ty;
char ss[10];struct Query{int index,u,v,t,ans;//ans是该条查询语句的答案
}query[maxk];struct Read{int u,v,xx,yy;
}read[maxn];bool cmp1(Query Q1,Query Q2)//按查询语句的t排序
{if(Q1.t==Q2.t) return Q1.index<Q2.index;return Q1.t<Q2.t;
}bool cmp2(Query Q1,Query Q2)//按查询语句的查询顺序排序
{return Q1.index<Q2.index;
}int find(int u)
{if(pre[u]==u) return u;int tmp=find(pre[u]);x[u]=x[u]+x[pre[u]];y[u]=y[u]+y[pre[u]];return pre[u]=tmp;
}void mix(int a,int b,int tx,int ty)
{int fa=find(a);int fb=find(b);if(fa!=fb){pre[fa]=fb;x[fa]=x[b]-x[a]+tx;y[fa]=y[b]-y[a]+ty;}
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);
#endifwhile(~scanf("%d%d",&n,&m)&&n){for(int i=0;i<=n;i++)pre[i]=i;memset(x,0,sizeof(x));memset(y,0,sizeof(y));for(int i=1;i<=m;i++){scanf("%d%d%d%s",&a,&b,&d,ss);if(ss[0]=='E'){tx=d;ty=0;}//这里对方向做了统一规定else if(ss[0]=='W'){tx=-d;ty=0;}else if(ss[0]=='S'){tx=0;ty=d;}else if(ss[0]=='N'){tx=0;ty=-d;}read[i].u=a;read[i].v=b;read[i].xx=tx;read[i].yy=ty;}scanf("%d",&k);for(int i=1;i<=k;i++){scanf("%d%d%d",&query[i].u,&query[i].v,&query[i].t);query[i].ans=0;query[i].index=i;//查询顺序标记}sort(query+1,query+k+1,cmp1);int now=1;for(int i=1;i<=k;i++){for(int j=now;j<=query[i].t;j++){a=read[j].u;b=read[j].v;tx=read[j].xx;ty=read[j].yy;mix(a,b,tx,ty);}int uu=query[i].u;int vv=query[i].v;if(find(uu)==find(vv))//uu和vv连通{query[i].ans=abs(x[uu]-x[vv])+abs(y[uu]-y[vv]);}else query[i].ans=-1;//printf("uu=%d x[uu]=%d y[uu]=%d vv=%d x[vv]=%d y[vv]=%d \n",uu,x[uu],y[uu],vv,x[vv],y[vv]);//printf("************\n");now=query[i].t+1;}sort(query+1,query+1+k,cmp2);for(int i=1;i<=k;i++)printf("%d\n",query[i].ans);}return 0;
}