

1
#include<iostream>
2
#include<algorithm>
3
#include<cmath>
4
#include<vector>
5
using namespace std;
6
#define maxn 1000000+10
7
8
9
struct SNode
10

{
11
int to;
12
int len;
13
SNode *next;
14
}graph[40000+10],depot[1000000];
15
16
int N,M,idx=0,allocate;
17
int E[maxn],L[maxn],H[maxn], dist[maxn], rmq[maxn][20];;
18
bool visited[maxn];
19
20
void dfs(int k,int level,int dis)
21

{
22
visited[k]=true;
23
H[k]=idx;
24
dist[k]=dis;
25
L[idx]=level;
26
E[idx]=k;
27
idx++;
28
for( SNode *p= graph[k].next ; p ;p=p->next )
{
29
if( !visited[ p->to ])
{
30
dfs(p->to ,level+1,dis+p->len );
31
L[idx]=level;
32
E[idx]=k;
33
idx++;
34
}
35
}
36
}
37
38
39
40
void ST(int n)
41

{
42
for(int i=0;i<n;i++)
43
rmq[i][0]=i;
44
for(int j=1; (1<<j) <=n;j++)
{
45
for(int i=0;i +(1<<j)-1 <n;i++)
{
46
if( L[ rmq[i][j-1] ] < L[rmq[ i+(1<<(j-1) ) ][j-1] ])
47
rmq[i][j]=rmq[i][j-1];
48
else
49
rmq[i][j]= rmq[i+(1<<(j-1) )][j-1] ;
50
}
51
}
52
}
53
54
55
56
int RMQ(int i,int j)
57

{
58
int k;
59
for(k = 0;(1 << k) <= (j - i + 1);++ k); -- k;
60
if( L[ rmq[i][k] ]< L[ rmq[ j-(1<<k)+1 ][k] ] )
61
return rmq[i][k];
62
else
63
return rmq[ j-(1<<k)+1 ][k] ;
64
}
65
66
int LCA(int i,int j)
67

{
68
if( H[i]>H[j])swap(i,j);
69
/**//*printf("RMQ %d %d %d\n",H[i],H[j],RMQ(H[i],H[j]) );*/
70
return E[ RMQ( H[i] ,H[j] ) ] ;
71
}
72
73
74
75
76
77
78
79
void initial()
80

{
81
for(int i=0;i<=N;i++)
82
graph[i].next =NULL;
83
memset(dist,0,sizeof(dist));
84
memset(visited,false,sizeof(visited));
85
idx=0;
86
allocate=0;
87
}
88
89
90
91
int main()
92

{
93
//freopen("dquery.6.in","r",stdin);
94
while(scanf("%d %d",&N,&M)!=EOF)
{
95
initial();
96
char s[10];
97
int x,y,len;
98
SNode *p;
99
for(int i=0;i<M;i++)
{
100
scanf("%d %d %d %s",&x,&y,&len,s);
101
p=&depot[allocate++];
102
p->len =len;
103
p->to =y;
104
p->next =graph[x].next ;
105
graph[x].next =p;
106
107
p=&depot[allocate++];
108
p->len =len;
109
p->to =x;
110
p->next =graph[y].next ;
111
graph[y].next =p;
112
}
113
dfs(1 ,0,0);
114
ST(idx);
115
int K;
116
scanf("%d",&K);
117
for(int i=0;i<K;i++)
{
118
scanf("%d %d",&x,&y);
119
int lca=LCA(x,y);
120
int ans=dist[x]+dist[y]-2*dist[lca] ;
121
printf("%d\n",ans);
122
}
123
}
124
return 0;
125
}
126
127
posted on 2009-08-13 09:55
iyixiang 阅读(179)
评论(0) 编辑 收藏 引用 所属分类:
acm