POJ 1984

• 自己审题问题极其严重

1.忽略了该题询问i行可能询问多次，
2.忽略了给出询问行不是按顺序的排序的，我以为是按顺序，

• 没有想出怎么用带权并查集做
• 根据给出的东南西北来维护dx横坐标到根节点距离 dy纵坐标到根节点距离,
• 路径压缩的时候dx dy一起压缩就行,主要是合并的时候根据题目给出的东南西北来确定dx dy
• 合并根节点 还是rala[ra] = rala[b] + s - rala[a]，本质的东西没有变(还是矢量 相加减)

  #include <iostream>
  #include <queue>
  #include <string.h>
  #include <algorithm>
      
  using namespace std;
  const int maxn = 4e4+10;
  
  int pre[maxn];
  long long  dx[maxn];
  long long  dy[maxn];
  struct point {
  	int time;
  	int u,v;
  	point () {
  	}
  	point (int a,int b,int c) {
  		u = a;
  		v = b;
  		time = c;
  	}
  	bool operator< (const point& t) const {
  		return time < t.time;
  	} 
  } p[maxn];
  struct node {
  	int u,v;
  	int  dist;
  	char dir;
  	node () {
  	}
  	node (int a,int b,int d,char c) {
  		u = a;
  		v = b;
  		dist = d;
  		dir = c;
  	}
  }e[maxn];
  
  int n,m,k;
  
  void init() {
  	memset(dx,0,sizeof dx);
  	memset(dy,0,sizeof dy);
  	for (int i=1; i<=n; i++) pre[i] = i;
  }
  int find(int x) {
  	int temp = pre[x];
  	if (pre[x] == x) return x;
  	pre[x] = find(pre[x]);
  	
  	dx[x] += dx[temp];
  	dy[x] += dy[temp];
  	
  	return pre[x]; 
  }
  void merge(int i) {
  	int a = e[i].u;
  	int b = e[i].v;
  	int ra = find(a);
  	int rb = find(b);
  	if (ra != rb) {
  		int tx=0,ty=0;
  		
  		if (e[i].dir == 'E') tx = e[i].dist;
  		else if (e[i].dir == 'W') tx = -e[i].dist;
  		else if (e[i].dir == 'S') ty = -e[i].dist;
  		else if (e[i].dir == 'N') ty = e[i].dist; 
  		
  		pre[ra] = rb;
  		dx[ra] = dx[b] - dx[a] + tx;
  		dy[ra] = dy[b] - dy[a] + ty;	
  	}
  }
  
  
  int main() {
  //	freopen("a.txt","r",stdin);
  	cin >> n >> m;
  	for (int i=1; i<=m; i++) {
  		int a,b,d;
  		char ch;
  		cin >> a >> b >> d >> ch;
  		node t(a,b,d,ch);
  		e[i] = t; 
  	}
  	
  	cin >> k;
  	for (int i=1; i<=k; i++) {
  		int a,b,c;
  		cin >> a >> b >> c;
  		point t(a,b,c);
  		p[i] = t;
  	} 
  	
  	sort(p+1,p+1+k);
  	
  	int time;
  	int u,v;
  	int cnt = 2;
  	
  	u = p[1].u;
  	v = p[1].v;
  	time = p[1].time;
  	
  	init();
  	 
  	for (int i=1; i<=m; i++) {
  		//建图
  		merge(i);
  		
  		while (time == i) { //忽略了 第i个可能会被问到多次的情况 
  			int ra = find(u);
  			int rb = find(v);
  
  			if (ra == rb) {
  				printf("%d\n",abs(dx[u]-dx[v])+abs(dy[u]-dy[v]) );
  			}
  			else {
  				printf("-1\n");
  			}
  			u = p[cnt].u;
  			v = p[cnt].v;
  			time = p[cnt].time;
  			cnt++;
  			if (cnt > k+1) break;
  		}
  	}
  	return 0;
  }