1 #include<iostream>
 2 #include<cstdio>
 3 #include<cassert>
 4 using namespace std;
 5 #define re(i,n) for(int i=0;i<n;i++)
 6 #define re1(i,n) for(int i=1;i<=n;i++)
 7 const int V = 1005;
 8 const int E = 1000005;
 9 template <typename T> inline void chkmax (T &a, T b) {if(a<b) a=b;}
10 int G[V][V],mx[V][V],low[V],vis[V],P[V];
11 struct edge{
12     int u,v;
13     edge(int U=0,int V=0) : u(U), v(V) {}
14 } num[E];
15 const int inf = ~0u>>2;
16 int n,m,q;
17 void prim(){
18     for(int i=0;i<n;i++){
19         low[i] = inf;
20         vis[i] = 0;
21     }
22     low[0] = 0;
23     for(int j=0;j<n;j++){
24         int s=-1, mn = inf;
25         for(int i=0;i<n;i++)
26             if(!vis[i] && mn > low[i]){
27                 s = i; mn = low[i];
28             }
29         assert(s!=-1);
30 //        cout<<"s: "<<s<<" "<<mn<<endl;
31 //        cout<<P[s]<<endl;
32         for(int i=0;i<n;i++) if(vis[i]){
33             mx[s][i] = max(mx[i][P[s]],mn);
34             mx[i][s] = mx[s][i];
35 //            cout<<"i: "<<i<<" "<<mx[i][s]<<endl;
36         }
37         
38         vis[s] = 1;
39         for(int i=0;i<n;i++) if(!vis[i] && G[s][i] < low[i]){
40             low[i] = G[s][i]; P[i] = s;
41         }
42     }
43 //    for(int i=0;i<n;i++) cout<<low[i]<<" "; cout<<endl;
44 }
45 int main(){
46     while(~scanf("%d%d%d",&n,&m,&q)){
47         int u,v,c;
48         for(int i=0;i<n;i++) for(int j=0;j<n;j++){
49             G[i][j] = inf;
50             mx[i][j] = 0;
51         }
52         for(int i=0;i<m;i++){
53             scanf("%d%d%d",&u,&v,&c);
54             u--;v--;
55             num[i] = edge(u,v);
56             if(c < G[u][v]) {
57                 G[u][v] = G[v][u] = c;
58             }
59         }
60         prim();
61 //        for(int i=0;i<n;i++) { for(int j=0;j<n;j++) cout<<mx[i][j]<<" "; cout<<endl;}
62         while(q--){
63             scanf("%d%d",&u,&v);
64             u--;
65             int a = num[u].u, b = num[u].v;
66             puts(mx[a][b] >= v?"Yes": "No");
67         }
68     }
69 }
70 

  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