這個是認真寫的...
1 // poj 2831 by figo in 5,19,2012
2 // template
3 #include<iostream>
4 #include<algorithm>
5 #include<cassert>
6 #include<cstdio>
7 #include<cstdlib>
8 using namespace std;
9 template <typename T> inline
void chkmax(T &a, T b){
if(a<b) a=b;}
10 // graph
11 const int V = 1005;
12 const int E = 200005;
13 int head[V],pnt[E],nxt[E],cost[E],flag[E];
14 int n,e;
15 void add_edge(
int u,
int v,
int c){
16 nxt[e] = head[u];
17 pnt[e] = v;
18 head[u] = e;
19 cost[e] = c;
20 e ++;
21 }
22 // kruskal
23 int parent[V];
24 struct edge{
25 int u,v,c,id;
26 edge() {}
27 edge(
int U,
int V,
int C,
int ID) : u(U), v(V), c(C), id(ID) {}
28 bool operator < (edge A)
const {
29 return c < A.c;
30 }
31 } num[E];
32 int find(
int x){
return x == parent[x] ? x : parent[x] = find(parent[x]);}
33 void kruskal(){
34 int len = 0;
35 for(
int u = 0; u< n; u++)
36 for(
int i = head[u]; i!=-1;i = nxt[i])
37 num[len++] = edge(u,pnt[i],cost[i],i);
38 assert(len == e);
39 sort(num, num+len);
40 for(
int i=0;i<n;i++)
41 parent[i] = i;
42 for(
int i=0;i<len;i++) flag[i] = 0;
43 for(
int i = 0; i< len; i++){
44 int u = num[i].u, v = num[i].v,id = num[i].id;
45 if(find(u) == find(v))
continue;
46 flag[id] = flag[id ^ 1] = 1;
47 parent[parent[u]] = parent[v];
48 }
49 }
50 // seg_ment tree
51 int seg[V<<2], M;
52 int find(
int l,
int r){
53 int ans = 0;
54 for(l += M-1, r += M+1; l^r^1; l>>=1, r>>=1){
55 if(~l&1) chkmax(ans,seg[l^1]);
56 if(r&1) chkmax(ans,seg[r^1]);
57 }
58 return ans;
59 }
60 void insert(
int pos,
int x){
61 pos += M;
62 seg[pos] = x;
63 while(pos>>=1){
64 seg[pos] = max(seg[pos << 1] , seg[pos << 1 | 1]);
65 }
66 }
67 // prepare
68 int deep[V],size[V],heavy[V],P[V];
69 void dfs(
int u,
int f){
70 size[u] = 1;
71 int mx = 0, s = -1;
72 for(
int i=head[u]; i!=-1;i = nxt[i]){
73 if(!flag[i] || pnt[i] == f)
continue;
74 int v = pnt[i];
75 P[v] = i^1;
76 deep[v] = deep[u] + 1;
77 dfs(v,u);
78 if(size[v] > mx){
79 mx = size[v];
80 s = i;
81 }
82 size[u] += size[v];
83 }
84 heavy[u] = s;
85 if(s!=-1) parent[pnt[s]] = u;
86 }
87 void prepare(){
88 kruskal();
89 for(
int i=0;i<n;i++) parent[i] = i;
90 deep[0] = 0;
91 P[0] = -1;
92 dfs(0,0);
93 for(
int i=30;i;i--)
if((1<<i) > n+1) M = 1<<i;
94 for(
int i=0;i<2*M;i++) seg[i] = 0;
95 int len = 1;
96 for(
int u = 0; u<n; u++)
if(heavy[u] == -1){
97 int v = u;
98 while(v && pnt[heavy[pnt[P[v]]]] == v){
99 insert(len,cost[P[v]]);
100 flag[P[v]] = flag[P[v]^1] = len ++;
101 v = pnt[P[v]];
102 }
103 }
104 }
105 // operator
106 int lca(
int u,
int v){
107 while(1){
108 int a = find(u), b = find(v);
109 if(a == b)
return deep[u]<deep[v] ? u : v;
110 else if(deep[a] > deep[b]) u = pnt[P[a]];
111 else v = pnt[P[b]];
112 }
113 }
114 int query(
int u,
int v){
115 int ans = 0;
116 // cout<<u<<" "<<v<<endl;
117 while(u != v){
118 //cout<<u<<endl;
119 int l = P[u];
120 if(pnt[heavy[pnt[P[u]]]] == u){
121 int p = find(u);
122 if(deep[p] < deep[v]) p = v;
123 // cout<<u<<" "<<p<<endl;
124 int r = heavy[p];
125 assert(flag[l] <= flag[r]);
126 int mx = find(flag[l],flag[r]);
127 chkmax(ans,mx);
128 u = p;
129 }
130 else {
131 chkmax(ans,cost[l]);
132 u = pnt[l];
133 }
134 }
135 //cout<<"ans:"<<ans<<endl;
136 return ans;
137 }
138 int ask(
int E,
int val){
139 int u = pnt[E<<1];
140 int v = pnt[E<<1|1];
141 int p = lca(u,v);
142 //cout<<u<<" "<<v<<" "<<p<<endl;
143 return val <= query(u,p) || val <= query(v,p);
144 }
145 // main
146 int main(){
147 int m,q,u,v,c;
148 while(~scanf("%d%d%d",&n,&m,&q)){
149 e= 0;
150 for(
int i=0;i<n;i++) head[i] = -1;
151 for(
int i=0;i<m;i++) {
152 scanf("%d%d%d",&u,&v,&c);
153 u--; v--;
154 add_edge(u,v,c);
155 add_edge(v,u,c);
156 }
157 prepare();
158 while(q--){
159 scanf("%d%d",&u,&v);
160 u--;
161 puts(ask(u,v) ? "Yes": "No");
162 }
163 }
164 return 0;
165 }
166