并查集的一個(gè)應(yīng)用，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1984
//并查集合的一個(gè)應(yīng)用

#include <stdio.h>
#include <math.h>

int p[40005];

typedef struct
{
    int x;
    int y;
}point;
point dis[40005];

void make ( int n )
{

    for ( int i=0; i<n; i++ )
    {
        p[i] = -1;
        dis[i].x = dis[i].y = 0; 
    }
}

int find ( int pre )
{

    if ( p[pre] < 0 )
    {
        return pre;
    }
    int root = find ( p[pre] );

    dis[pre].x += dis[ p[pre] ].x;
    dis[pre].y += dis[ p[pre] ].y;

    p[pre] = root;

    return root;
}

void un ( int a, int b, int l, char done )
{

    int ra = find ( a );
    int rb = find ( b );
    point oldp, newp;
    
    oldp.x = dis[b].x;
    oldp.y = dis[b].y;

    if ( done == 'E' )
    {
        newp.x = dis[a].x + l;
        newp.y = dis[a].y;
    }
    else if ( done == 'S' )
    {
        newp.x = dis[a].x;
        newp.y = dis[a].y - l;
    }
    else if ( done == 'W' )
    {
        newp.x = dis[a].x - l;
        newp.y = dis[a].y;
    }
    else
    {
        newp.x = dis[a].x;
        newp.y = dis[a].y + l;
    }

    p[rb] = ra;
    dis[rb].x = newp.x - oldp.x;
    dis[rb].y = newp.y - oldp.y;
}

struct
{
    int a;
    int b;
    int l;
    char done;
}rela[40005];

struct
{
    int next;
    int last;
}head[40005];

struct
{
    int a;
    int b;
    int addr;
    int i;
    int next;
}po[10005];
int now;

void inith ( int n )
{

    now = 0;
    for ( int i=0; i<n; i++ )
    {
        head[i].next = head[i].last = -1;
    }
}

void add ( int a, int b, int i, int addr )
{

    po[now].a = a;
    po[now].b = b;
    po[now].addr = addr;
    po[now].next = -1;

    if ( head[i].next == -1 )
    {
        head[i].next = now;
    }
    else
    {
        po[ head[i].last ].next = now;
    }
    head[i].last = now ++;
}

int que[10005];

int main ()
{

    int n, m;
    int a, b, l;
    char in[5];
    int k;
    int f1, f2, di;

    while ( scanf ( "%d%d", &n, &m ) != EOF )
    {
        for ( int i=0; i<m; i++ )
        {
            scanf ( "%d%d%d%s", &a, &b, &l, in );
            rela[i].a = a-1;
            rela[i].b = b-1;
            rela[i].l = l;
            rela[i].done = in[0];
        }
        
        make ( n );
        inith ( m );
        scanf ( "%d", &k );
        for ( i=0; i<k; i++ )
        {
            scanf ( "%d%d%d", &f1, &f2, &di );
            add ( f1-1, f2-1, di-1, i );
        }
        for ( i=0; i<m; i++ )
        {
            if ( find ( rela[i].a ) != find ( rela[i].b ) )
            {
                un ( rela[i].a, rela[i].b, rela[i].l, rela[i].done );
            }
            for ( int j=head[i].next; j!=-1; j=po[j].next )
            {
                if ( find ( po[j].a ) != find ( po[j].b ) )
                {
                    que[po[j].addr] = -1;
                }
                else
                {
                    int ans = abs ( dis[ po[j].a ].x - dis[ po[j].b ].x ) + abs ( dis[ po[j].a ].y - dis[ po[j].b ].y );
                    que[po[j].addr] = ans;
                }
            }
        }
        for ( i=0; i<k; i++ )
        {
            printf ( "%d\n", que[i] );
        }
    }
    return 0;
}