#include  < iostream >
#include 
< vector >

using   namespace  std;

#define  N 40010
typedef pair
< int , int >  PAIR;

int  m, n;
vector
< PAIR >  query[N], map[N];

int  uset[N] =  { 0 }, acs[N], flag[N] =  { 0 }, dis[N] =  { 0 }, ans[N], visite[N] = { 0 };

int  find(  int  x ){
    
while ( x !=  uset[x] ) x =  uset[x];
    
return  x; }

void  join(  int  x,  int  y ){  uset[ find(x) ] =  uset[ find(y) ]; }

void  dfs(  int  u,  int  d ){
    uset[u]
=  u; acs[u] =  u; dis[u] =  d; visite[u] =   1 ;
    
for ( size_t i =   0 ; i <  map[u].size();  ++ i ){
        
int  v =  map[u][i].first, w =  map[u][i].second;
        
if ! visite[v] ){
            dfs( v, d
+  w );
            join( u, v ); acs[ find(u) ]
=  u;  }
    }
    
    flag[u]
=   1 ;
    
for ( size_t i =   0 ; i <  query[u].size();  ++ i ){
        
int  v =  query[u][i].first, w =  query[u][i].second;
        
        
if ( flag[v] ) ans[w] =  dis[u] +  dis[v] -   2 *  dis[ acs[ find(v) ] ];
    }    
}

int  main(){
    
int  u, v, d;
    
char  s[ 10 ];
    
    scanf(
" %d%d " , & n, & m);
    
while ( m --  ){
        scanf(
" %d%d%d%s " , & u, & v, & d,s );
        map[u].push_back( PAIR(v,d) );
        map[v].push_back( PAIR(u,d) );
    }
    
    scanf(
" %d " , & m );
    
for int  i =   1 ; i <=  m;  ++ i ){
        scanf(
" %d%d " , & u, & v );
        query[u].push_back( PAIR(v,i) );
        query[v].push_back( PAIR(u,i) );
    }
    memset( flag, 
0 sizeof (flag) );
    memset( visite, 
0 sizeof (visite) );
    
    dfs( 
1 0  ); 
    
for int  i =   1 ; i <=  m;  ++ i ) printf( " %d\n " , ans[i] );
    
    
return   0 ;
}
posted on 2009-07-20 10:56 Darren 阅读(333) 评论(0)  编辑 收藏 引用 所属分类: 图论数据结构

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理