【杭电oj2586】How far away ？

灰太狼 2022-09-26 02:56 93阅读 0赞

# How far away ？ #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 13230 Accepted Submission(s): 4956**

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

[ECJTU 2009 Spring Contest][]

Recommend

lcy | We have carefully selected several similar problems for you: [3486][] [2874][] [2888][] [3234][] [2818][]

tarjan离线算法解决LCA问题，dfs+邻接表+并查集。核心代码是dfs部分，对dfs理解深刻的话应该能看懂，实在不懂就自己心算一下详细过程。

其他解决LCA问题的方法还有很多，比如转化为RMQ问题，看看自己对那个算法理解深刻去应用。

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int N = 40000+10;
    const int M = 220;
    int head[N],head1[N],dis[N],LCA[N],father[N];
    bool vis[N];
    int n,m,cnt;
    struct Edge{
    	int from,to;
    	int next;
    	int val;
    };
    struct Edge1{
    	int u,v;
    	int num;
    	int next;
    };
    Edge edge[N*2];
    Edge1 edge1[M*2];
    void add_edge(int u,int v,int val){
    	edge[cnt].from=u;
    	edge[cnt].to=v;
    	edge[cnt].val=val;
    	edge[cnt].next=head[u];
    	head[u]=cnt++;
    }
    void add_ans(int u,int v,int num){
    	edge1[cnt].u=u;
    	edge1[cnt].v=v;
    	edge1[cnt].num=num;
    	edge1[cnt].next=head1[u];
    	head1[u]=cnt++;
    } 
    int find(int x){
    	//return x==father[x]?x:find(father[x]); 
    	int r=x;
    	while(r!=father[r]){
    		r=father[r];
    	}
    	return r;
    //	if(x!=father[x]){
    //		x=father[x];
    //	}
    //	return father[x];
    }
    void tarjan(int k){
    	vis[k]=1;
    	father[k]=k;
    	for(int i=head1[k];i!=-1;i=edge1[i].next){
    		int v=edge1[i].v;
    		if(vis[v]){
    			LCA[edge1[i].num]=find(v);
    		}
    	}
    	for(int i=head[k];i!=-1;i=edge[i].next){
    		int to=edge[i].to;
    		if(!vis[to]){
    			dis[to]=dis[k]+edge[i].val;
    			tarjan(to);
    			father[to]=k;
    		}
    	}
    }
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d%d",&n,&m);
    		int a,b,c;
    		cnt=0;
    		memset(head,-1,sizeof(head));
    		memset(dis,0,sizeof(dis)); 
    		for(int i=0;i<n-1;i++){
    			scanf("%d%d%d",&a,&b,&c);
    			add_edge(a,b,c);
    			add_edge(b,a,c);
    		}
    		dis[1]=0;
    		cnt=0;
    		memset(head1,-1,sizeof(head1));
    		for(int i=1;i<=m;i++){
    			scanf("%d%d",&a,&b);
    			add_ans(a,b,i);
    			add_ans(b,a,i);
    		}
    		memset(vis,0,sizeof(vis));
    		tarjan(1);
    		for(int i=1;i<=m*2;i+=2){
    			a=edge1[i].u;
    			b=edge1[i].v;
    			c=edge1[i].num;
    			printf("%d\n",dis[a]+dis[b]-2*dis[LCA[c]]);
    		}
    	}
    	return 0;
    }

[ECJTU 2009 Spring Contest]: http://acm.hdu.edu.cn/search.php?field=problem&key=ECJTU+2009+Spring+Contest+&source=1&searchmode=source
[3486]: http://acm.hdu.edu.cn/showproblem.php?pid=3486
[2874]: http://acm.hdu.edu.cn/showproblem.php?pid=2874
[2888]: http://acm.hdu.edu.cn/showproblem.php?pid=2888
[3234]: http://acm.hdu.edu.cn/showproblem.php?pid=3234
[2818]: http://acm.hdu.edu.cn/showproblem.php?pid=2818