CodeStream

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  12 随笔 :: 0 文章 :: 6 评论 :: 0 Trackbacks

 链接

How far away ?

Time Limit: 2000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 559    Accepted Submission(s): 218

Problem Description

There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.

 

Input

First line is a single integer T(T<=10), indicating the number of test cases.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j. 


Output

For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.



 

Sample Input
2 3 2 1 2 10 3 1 15 1 2 2 3 2 2 1 2 100 1 2 2 1

 
Sample Output

10
25
100
100

 
 
Source
 


 

题目大意:
n个点,n-1条路形成了一棵树,然后又m个询问:(x,y)输出x到y的最短距离,典型的LCA问题,用Tarjan解决,时间复杂度为O(n+m)
代码:

#include <iostream>
#include 
<stdio.h>
using namespace std;

#define max_size 40002

int cnt, head[max_size], next[max_size];
int set[max_size], d[max_size], ans[201];
bool fals[max_size];

struct Edge
{
    
int v;
    
int w;
    
int pre;
}
eg[2*max_size], ask[404];

int find(int x)
{
    
if (x == set[x])
        
return x;
    
else
        
set[x] = set[set[x]];
    
return find(set[x]);
}



void add_edge(int x, int y, int z)
{
    eg[cnt].v 
= y;
    eg[cnt].w 
= z;
    eg[cnt].pre 
= head[x];
    head[x] 
= cnt++;
}


void add_ask(int x, int y, int cast)
{
    ask[cnt].v 
= y;
    ask[cnt].w 
= cast;
    ask[cnt].pre 
= next[x];
    next[x] 
= cnt++;
}


void Tarjan(int k)
{
    fals[k] 
= true;

    
if (head[k] == 0)return ;

    
int i, x, root;

    
for (i = next[k]; i != 0; i = ask[i].pre)
    
{
        x 
= ask[i].v;
        
if (!fals[x])continue;
        root 
= find(x);
        ans[ask[i].w] 
= d[x] + d[k] - 2*d[root];
    }


    
for (i = head[k]; i != 0; i = eg[i].pre)
    
{
        x 
= eg[i].v;
        
if (fals[x])continue;
        d[x] 
= d[k] + eg[i].w;
        Tarjan(x);
        x 
= find(x);
        
set[x] = k;
    }


}


int main()
{
    
int i, m, n;
    
int x, y, z;
    
int t;
    cin 
>> t;
    
while (t--)
    
{
        cin 
>> n >> m;
        
for (i = 0; i <= n; i++)
        
{
            head[i] 
= next[i] = 0;
            
set[i] = i;
            fals[i] 
= false;
        }

        
        cnt 
= 1;
        
for (i = 1; i < n; i++)
        
{
            scanf(
"%d%d%d"&x, &y, &z);
            add_edge(x, y, z);
            add_edge(y, x, z);
        }

        cnt 
= 1;
        
for (i = 1; i <= m; i++)
        
{
            scanf(
"%d%d"&x, &y);
            add_ask(x, y, i);
            add_ask(y, x, i);
        }

        d[
1= 0;
        Tarjan(
1);

        
for (i = 1; i <= m; i++)
            printf(
"%d\n", ans[i]);
    }

    
return 0;
}
posted on 2011-03-24 15:44 CodeStream 阅读(573) 评论(0)  编辑 收藏 引用 所属分类: acm_LCA

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