1
#include<iostream>
2#include<algorithm>
3#include<cmath>
4#include<vector>
5using namespace std;
6#define maxn 1000000+10
7
8
9struct SNode
10
{
11
int to;
12 int len;
13 SNode *next;
14
}graph[40000+10],depot[1000000];
15
16int N,M,idx=0,allocate;
17int E[maxn],L[maxn],H[maxn], dist[maxn], rmq[maxn][20];;
18bool visited[maxn];
19
20void 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
40void 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
56int 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
66int 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
79void 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
91int 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
127posted on 2009-08-13 09:55
iyixiang 阅读(176)
评论(0) 编辑 收藏 引用 所属分类:
acm