How far away ?
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 20971 Accepted Submission(s): 8245
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.
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
思路:
Tarjan模板题,Tarjan还是比较好理解的。。。
推荐一篇很不错的博客:
https://www.cnblogs.com/JVxie/p/4854719.html
实现代码:
#include<bits/stdc++.h> using namespace std; #define ll long long const int M = 1e5+10; struct node{ int to,next,w,sum; }; int n,m,cnt1,cnt2; node e[M<<1]; //双向边 node q[M]; //询问的边 int fa[M],head[M<<1],qhead[M]; bool vis[M]; ll d[M],res[M]; int find(int x){ return fa[x] == x?x:fa[x] = find(fa[x]); } void add(int u,int v,int w){ e[++cnt1].w=w;e[cnt1].to=v;e[cnt1].next=head[u];head[u]=cnt1; e[++cnt1].w=w;e[cnt1].to=u;e[cnt1].next=head[v];head[v]=cnt1; } void add1(int u,int v){ q[++cnt2].to=v;q[cnt2].next=qhead[u];qhead[u]=cnt2; } void dfs(int u,int fa,ll w){ d[u] = w; for(int i = head[u];i!=-1;i=e[i].next){ int v = e[i].to; if(v==fa) continue; dfs(v,u,w+e[i].w); } } void tarjan(int u){ fa[u] = u; vis[u] = 1; for(int i = head[u];i!=-1;i=e[i].next){ int v = e[i].to; if(!vis[v]){ tarjan(v); fa[v] = u; } } for(int i = qhead[u];i!=-1;i=q[i].next){ int v = q[i].to; if(vis[v]){ q[i].sum = find(v); res[i] = d[u] + d[v] - 2*d[q[i].sum];//两者的距离 //cout<<i<<" "<<res[i]<<endl; } } } void solve(){ for(int i = 0;i < n;i ++) fa[i] = i; memset(head,-1,sizeof(head)); memset(qhead,-1,sizeof(qhead)); memset(vis,0,sizeof(vis)); cnt1 = cnt2 = 0; int u,v,w; for(int i = 1;i < n;i ++){ cin>>u>>v>>w; add(u,v,w); } for(int i = 0;i < m;i ++){ cin>>u>>v; add1(u,v); } dfs(1,-1,0); tarjan(1); } int main() { int t; ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>t; while(t--){ cin>>n>>m; solve(); for(int i = 1;i <= m;i ++){ cout<<res[i]<<endl; } } return 0; }