路径归并,地址: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 ( 
00 );

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

    }


    
return 0;
}