|
|
思路： 每次新增點a -> b的時候，union (b, a)，節點中保存的是距離的偏移量。 查詢a, b的關系的時候，如果a, b不是一類，就輸出-1，如果是的話，就將a，b的偏移量相加然后輸出。
 #include <stdio.h>
  struct node  {
 int a, b;
struct node *next;
 };
struct node nodes[10032];
struct {
int from, to, len;
char dir;
struct node *query;
} arr[40032];
struct {
int parent, x, y;
} set[400032];
int N, M;
__inline int abs(int i)
{
return i > 0 ? i : -i;
}
int set_find(int i)
{
int r, p;
p = set[i].parent;
if (!p)
return i;
r = set_find(p);
set[i].x += set[p].x;
set[i].y += set[p].y;
set[i].parent = r;
return r;
}
void set_union(int from, int to, int x, int y)
{
int r = set_find(to);
set[r].parent = from;
set[r].x = x - set[to].x;
set[r].y = y - set[to].y;
}
int main()
{
int i, j, k, ia, ib, x, y;
char str[16];
struct node *t, **pt;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &M);
  for (i = 1; i <= M; i++) {
scanf("%d%d%d%s", &arr[i].from, &arr[i].to, &arr[i].len, str);
arr[i].dir = str[0];
 }
scanf("%d", &k);
for (i = 0; i < k; i++) {
scanf("%d%d%d", &nodes[i].a, &nodes[i].b, &j);
for (pt = &arr[j].query; *pt; pt = &(*pt)->next);
*pt = &nodes[i];
}
for (i = 1; i <= M; i++) {
switch (arr[i].dir) {
case 'E': x = arr[i].len; y = 0; break;
case 'W': x = -arr[i].len; y = 0; break;
case 'N': x = 0; y = arr[i].len; break;
case 'S': x = 0; y = -arr[i].len; break;
}
set_union(arr[i].from, arr[i].to, x, y);
for (t = arr[i].query; t; t = t->next) {
ia = set_find(t->a);
ib = set_find(t->b);
if (ia != ib)
j = -1;
else
j = abs(set[t->a].x - set[t->b].x) + abs(set[t->a].y - set[t->b].y);
printf("%d\n", j);
}
}
return 0;
}
|