题目描述的如此蛋疼。。。
关系并查集，用cx和cy数组记录点与根结点的相对位置，然后根据输入依次合并，当碰到询问时便计算距离，若不在同一集合中，即无法确定相对位置。
code:
#include<cstdio> #include<cstring> int p[ 40001], cx[ 40001], cy[ 40001] ; int f1[ 10001], f2[ 10001], fi[ 10001] ; struct edge{ int s, e, l ; char d ; }q[ 40001] ; int abs( int a){ return a> 0?a:-a ; } void make_set( int n){ for( int i= 0; i<=n+ 1; i++){ p[i] = i ; cx[i] = cy[i] = 0 ; } } int find_set( int x){ int temp ; if(x!=p[x]){ temp = p[x] ; p[x] = find_set(p[x]) ; cx[x] = cx[temp] + cx[x] ; cy[x] = cy[temp] + cy[x] ; } return p[x] ; } void union_set( int x){ int a = q[x].s ; int b = q[x].e ; int pa = find_set(a) ; int pb = find_set(b) ; p[pb] = pa ; cx[pb] = cx[a] - cx[b] ; cy[pb] = cy[a] - cy[b] ; switch(q[x].d){ case ' E ':cx[pb] += q[x].l ; break ; case ' W ':cx[pb] -= q[x].l ; break ; case ' N ':cy[pb] += q[x].l ; break ; case ' S ':cy[pb] -= q[x].l ; break ; } return ; } int main(){ int n, m, k, i, j, t, x, y, z, tx, ty ; while(~scanf( " %d%d ", &n, &m)){ make_set(n) ; for(i= 1; i<=m; i++) scanf( " %d %d %d %c ", &q[i].s, &q[i].e, &q[i].l, &q[i].d) ; scanf( " %d ", &t) ; for(i= 0; i<t; i++) scanf( " %d%d%d ", &f1[i], &f2[i], &fi[i]) ; int temp = 0 ; for(i= 1; i<=m; i++){ tx = find_set(q[i].s) ; ty = find_set(q[i].e) ; if(tx!=ty) union_set(i) ; while(fi[temp]==i){ tx = find_set(f1[temp]) ; ty = find_set(f2[temp]) ; if(tx!=ty) printf( " -1\n ") ; else{ tx = abs(cx[f1[temp]] - cx[f2[temp]]) ; ty = abs(cy[f1[temp]] - cy[f2[temp]]) ; printf( " %d\n ", tx + ty) ; } temp ++ ; } } } return 0 ;}