洛谷P1967 货车运输

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=10005;
 4 const int maxm=100005; 
 5 const int INF=0x3f3f3f3f;
 6 inline void read(int &tmp)
 7 {
 8     int x=1;char c=getchar();
 9     for(tmp=0;!isdigit(c);c=getchar()) if(c=='-') x=-1;
10     for(;isdigit(c);tmp=tmp*10+c-48,c=getchar());
11     tmp*=x;
12 }
13 struct edge{int to,dis,nex;}e[maxm];
14 int head[maxn],tot;
15 void add(int x,int y,int z) {e[++tot].to=y;e[tot].nex=head[x];e[tot].dis=z;head[x]=tot;}
16 int n,m,T,ID[maxn],tree,w[maxn],size[maxn],Min[maxn][30],f[maxn][30],deep[maxn];
17 typedef pair<int,int> P;
18 priority_queue< P >q;
19 bool v[maxn];
20 void Prim(int k)
21 {
22     if(ID[k]) return;
23     ++tree;ID[k]=tree;
24     w[k]=INF;q.push(make_pair(INF,k));
25     int Top,lastTop=0;
26     while(!q.empty())
27     {
28         Top=q.top().second;q.pop();
29         if(v[Top]) continue;
30         v[Top]=1;ID[Top]=tree;f[Top][0]=lastTop;++size[tree];
31         deep[Top]=deep[lastTop]+1;Min[Top][0]=w[Top];
32         lastTop=Top;
33         for(int i=head[Top];i;i=e[i].nex)
34             if(e[i].dis>w[e[i].to]) {w[e[i].to]=e[i].dis;q.push(make_pair(w[e[i].to],e[i].to));}
35     }
36 }
37 void init()
38 {
39     for(int j=1;(1<<j)<=n;++j)
40         for(int i=1;i<=n;++i)
41         {
42             if(f[i][j-1]) 
43             {
44                 f[i][j]=f[f[i][j-1]][j-1];
45                 Min[i][j]=min(Min[i][j-1],Min[f[i][j-1]][j-1]); 
46             }
47             if(!Min[i][j]) Min[i][j]=Min[i][j-1];
48         }
49 }
50 int LCA(int x,int y)
51 {
52     int nowtree=ID[x],ans=INF;
53     if(deep[x]<deep[y]) swap(x,y);
54     int i;for(i=0;(1<<i)<=size[nowtree];++i);--i;
55     for(int j=i;j>=0;--j)
56         if(deep[x]-(1<<j)>=deep[y]) ans=min(ans,Min[x][j]),x=f[x][j];
57     if(x==y) return ans;
58     for(int j=i;j>=0;--j)
59         if(f[x][j]&&f[x][j]!=f[y][j]) ans=min(ans,min(Min[x][j],Min[y][j])),x=f[x][j],y=f[y][j];
60     return ans;
61 }
62 int main()
63 {
64     read(n),read(m);
65     for(int i=1,x,y,z;i<=m;++i) read(x),read(y),read(z),add(x,y,z),add(y,x,z);
66     for(int i=1;i<=n;++i) Prim(i);
67     init();
68     read(T);
69     while(T--)
70     {
71         int x,y;read(x),read(y);
72         if(ID[x]!=ID[y]) {printf("%d
",-1);continue;}
73         printf("%d
",LCA(x,y)); 
74     }
75     return 0;
76 }