// tarjan
1
#include<iostream>
2#include<algorithm>
3#include<cmath>
4#include<vector>
5using namespace std;
6#define maxn 400000+10
7
8
9struct SNode
10
{
11
int to;
12 int len;
13 SNode *next;
14
}node[maxn],graph[maxn],query[maxn],depot[1000000];
15// query node len== query order
16int N,M,allocate;
17int lca[maxn],parent[maxn], dist[maxn];
18bool visited[maxn];
19bool black[maxn];
20
21int Find(int x)
22{
23
if( parent[x]!=x ){
24 parent[x]=Find( parent[x]);
25
}
26 return parent[x];
27}
28
29void initial()
30{
31 for(int i=0;i<=N;i++){
32 graph[i].next=NULL;
33 query[i].next=NULL;
34 parent[i]=i;
35 visited[i]=false;
36 black[i]=false;
37 }
38 allocate=0;
39}
40
41
42void tarjan(int u)
43{
44 visited[u]=true;
45 int v;
46 SNode *p;
47 for(p=graph[u].next ;p; p=p->next ){
48 v=p->to ;
49 if( !visited[v]){
50 dist[v]=dist[u]+p->len ;
51 tarjan(v);
52 parent[v]=u;
53 }
54 }
55 black[u]=true;
56 for(p=query[u].next ;p; p=p->next ){
57 v=p->to ;
58 if( black[v] ){
59 lca[ p->len ]= Find(v);
60 }
61 }
62}
63
64
65int main()
66{
67 //freopen("dquery.3.in","r",stdin);
68 while(scanf("%d %d",&N,&M)!=EOF){
69 initial();
70 char s[10];
71 int x,y,len;
72 SNode *p;
73 for(int i=0;i<M;i++){
74 scanf("%d %d %d %s",&x,&y,&len,s);
75 p=&depot[allocate++];
76 p->len =len;
77 p->to =y;
78 p->next =graph[x].next ;
79 graph[x].next =p;
80
81 p=&depot[allocate++];
82 p->len =len;
83 p->to =x;
84 p->next =graph[y].next ;
85 graph[y].next =p;
86 }
87
88 int K;
89 scanf("%d",&K);
90 for(int i=0;i<K;i++){
91 scanf("%d %d",&x,&y);
92 node[i].len =x;node[i].to =y;
93 p=&depot[allocate++];
94 p->len =i;
95 p->to =y;
96 p->next =query[x].next ;
97 query[x].next =p;
98
99 p=&depot[allocate++];
100 p->len =i;
101 p->to =x;
102 p->next =query[y].next ;
103 query[y].next =p;
104 }
105 tarjan(1);
106 int u,v;
107 for(int i=0;i<K;i++){
108 u=node[i].len ,v=node[i].to ;
109 printf("%d\n",dist[u]+dist[v]-2*dist[ lca[i] ] );
110 }
111 }
112 return 0;
113}
114
115posted on 2009-08-13 09:46
iyixiang 阅读(226)
评论(0) 编辑 收藏 引用 所属分类:
acm