路徑歸并，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1986
#include <stdio.h>

const int LEN = 40005;

int p[LEN];

void make ( int n )
{
    
    for ( int i=0; i<n; i++ )
    {
        p[i] = -1;
    }
}

int find ( int a )
{

    if ( p[a] < 0 )
    {
        return a;
    }
    int r = find ( p[a] );
    p[a] = r;

    return r;
}

void un ( int a, int b )
{

    int ra = find ( a );
    int rb = find ( b );

    p[rb] = ra;
}

struct
{
    int c;/*記錄結點的入度*/
    int last;/*記錄最后一個節點的地址*/
    int next;
}tab[LEN];/*鄰接鏈表頭,記錄最后一個節點的地址*/
typedef struct
{
    int num;
    int dis;//記錄邊的長度
    int addr;//記錄位置
    int next;
}type;
type node[LEN*2];
int next1; /*下一個可以使用的位置*/

void initm ( int n )
{

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

void adde ( int b, int e, int dis )/*增加一條邊*/
{

    node[next1].num = e;
    node[next1].next = -1;
    node[next1].dis = dis;
    if ( tab[b].next >= 0 )
    {
        node[ tab[b].last ].next = next1;
    }
    else
    {
        tab[b].next = next1;
    }
    tab[b].last = next1;
    tab[e].c ++;
    next1 ++;
}

struct
{
    int next;
    int last;
}que[LEN];
type q[LEN*2];
int next2;

void initq ( int n )
{

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

void addq ( int b, int e, int addr )/*增加一個問題*/
{

    q[next2].num = e;
    q[next2].next = -1;
    q[next2].addr = addr;
    if ( que[b].next >= 0 )
    {
        q[ que[b].last ].next = next2;
    }
    else
    {
        que[b].next = next2;
    }
    que[b].last = next2;
    next2 ++;
}

int color[LEN];//并且記錄從根結點到當前結點走的距離

int di[LEN];//記錄根結點到當前結點的距離

int used[LEN];//距離是否訪問過

int qustion[LEN];//記錄問題的答案

void initc ( int n )
{

    for ( int i=0; i<n; i++ )
    {
        color[i] = 0;
        di[i] = 0;
        used[i] = 0;
    }
    used[0] = 1;
}

void lca ( int p, int dis )
{

    di[p] = dis;
    for ( int i=tab[p].next; i!=-1; i=node[i].next )
    {
        if ( ! used[ node[i].num ] )
        {
            used[ node[i].num ] = 1;
            lca ( node[i].num, dis + node[i].dis );
            un ( p, node[i].num );
        }
    }

    for ( i=que[p].next; i!=-1; i=q[i].next )
    {
        if ( color[ q[i].num ]  )
        {
            qustion[ q[i].addr ] = di[p] + di[ q[i].num ] - 2 * di[ find ( q[i].num ) ];
        }
    }
    color[p] = 1;
}

int main ()
{

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

    while ( scanf ( "%d%d", &n, &m ) != EOF )
    {
        initm ( n );
        for ( i=0; i<m; i++ )
        {
            scanf ( "%d%d%d%s", &a, &b, &l, in );
            adde ( a-1, b-1, l );
            adde ( b-1, a-1, l );
        }

        scanf ( "%d", &k );
        initq ( n );
        for ( i=0; i<k; i++ )
        {
            scanf ( "%d%d", &f1, &f2 );
            addq ( f1-1, f2-1, i );
            addq ( f2-1, f1-1, i );
        }

        make ( n );
        initc ( n );
        lca ( 0, 0 );

        for ( i=0; i<k; i++ )
        {
            printf ( "%d\n", qustion[i] );
        }
    }

    return 0;
}