一、題目描述
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
二、分析
用Tarjan解決的LCA問題，詳細(xì)算法：LCA問題。
三、代碼
1
#include<iostream>
2#include<list>
3using namespace std;
4struct node
5
{
6
int v, d;
7
void init(int vv, int dd) {v = vv; d = dd;};
8
};
9int t, n, m, v1, v2, len;
10list<node> g[40001];
11list<node> query[40001];
12int dis[40001];
13int res[201][3];
14int parent[40001];
15bool visit[40001];
16int find(int k)
17{
18 if(parent[k] == k)
19 return k;
20 return parent[k] = find(parent[k]);
21}
22void tarjan(int u)
23{
24 if(visit[u]) return;
25 visit[u] = true;
26 parent[u] = u;
27 list<node>::iterator it = query[u].begin();
28 while(it != query[u].end())
29 {
30 if(visit[it->v])
31 res[it->d][2] = find(it->v);
32 it++;
33
}
34 it = g[u].begin();
35 while(it != g[u].end())
36 {
37 if(!visit[it->v])
38 {
39 dis[it->v] = min(dis[it->v], dis[u] + it->d);
40 tarjan(it->v);
41 parent[it->v] = u;
42 }
43 it++;
44 }
45}
46int main()
47{
48 scanf("%d", &t);
49 while(t--)
50 {
51 scanf("%d%d", &n, &m);
52 for(int i=1; i<=n; i++)
53 g[i].clear();
54 for(int i=1; i<=m; i++)
55 query[i].clear();
56 for(int i=1; i<n; i++)
57 {
58 scanf("%d%d%d", &v1, &v2, &len);
59 node n1; n1.init(v2, len);
60 g[v1].push_back(n1);
61 node n2; n2.init(v1, len);
62 g[v2].push_back(n2);
63 }
64 for(int i=1; i<=m; i++)
65 {
66 scanf("%d%d", &v1, &v2);
67 res[i][0] = v1;
68 res[i][1] = v2;
69 node n1; n1.init(v2, i);
70 query[v1].push_back(n1);
71 node n2; n2.init(v1, i);
72 query[v2].push_back(n2);
73 }
74 memset(visit, 0, sizeof(visit));
75 memset(dis, 0x7f, sizeof(dis));
76 dis[1] = 0;
77 tarjan(1);
78 for(int i=1; i<=m; i++)
79 printf("%d\n", dis[res[i][0]] + dis[res[i][1]] - 2*dis[res[i][2]]);
80 }
81}
posted on 2009-07-02 22:39
Icyflame 閱讀(1335)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告