# 希望更丰富的展现？使用Markdown
by 糪眾脦颰罷 @ 2018-11-08 21:30:26
##### 只有一部分Markdown是最骚的
by zyxzrzxm @ 2018-11-08 21:35:52
```
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int,int> pii;
int n,m,k;
struct node
{
int x,y,v;
node(int a,int b,int c)
{
x=a;
y=b;
v=c;
}
node()
{}
friend bool operator<(node a,node b)
{
return a.v>b.v;
}
};
int f[10001];
int s;int q;
vector<node> que;
int find (int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void mer(int x,int y)
{
x=find(x);
y=find(y);
if(x==y) return ;
f[x]=y;
}
vector<pii> v[10001];
int fa[10001][25];
int re[10001][25];
int d[10001];
void dfs(int pos,int faa)
{
for(int i=0;i<v[pos].size();i++)
{
if(v[pos][i].first==faa)
continue;
d[v[pos][i].first]=d[pos]+1;
re[v[pos][i].first][0]=v[pos][i].second;
fa[v[pos][i].first][0]=pos;
dfs(v[pos][i].first,pos);
}
}
int lca(int x,int y)
{
int res=0x3f3f3f3f;
if(d[x]>d[y])
swap(x,y) ;
for(int i=20;i>=0;i--)
{
if((d[y]-d[x])&(1<<i))
{
res=min(res,re[y][i]);
y=fa[y][i];
}
}
if(x==y) return res;
for(int i=20;i>=0;i--)
{
if(fa[x][i]==fa[y][i])
continue;
res=min(res,re[x][i]);
res=min(res,re[y][i]) ;
x=fa[x][i];
y=fa[y][i];
}
res=min(res,re[x][0]);
res=min(res,re[y][0]);
return res;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
que.push_back(node(x,y,z)) ;
}
sort(que.begin(),que.end());
for(vector<node>::iterator i=que.begin();i!=que.end();i++)
{
int x=i->x;
int y=i->y;
int vv=i->v;
if(find(x)==find(y)) continue;
mer(x,y);
v[x].push_back(pii(y,vv));
v[y].push_back(pii(x,vv));
}
memset(re,0x3f,sizeof(re));
for(int i=1;i<=n;i++)
if(fa[i][0]==0)
dfs(i,i);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=20;j++)
{
fa[i][j]=fa[fa[i][j-1]][j-1];
re[i][j]=min(re[i][j-1],re[fa[i][j-1]][j-1]);
}
}
cin>>q;
while(q--)
{
int x,y;
scanf("%d%d",&x,&y);
if(find(x)!=find(y)) {
cout<<-1<<endl;
}
else
cout<<lca(x,y)<<endl;
}
}
```
by toowater @ 2018-11-08 21:36:36