全部RE,实在找不出来,求助。
#include<bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
#define fo(i,e) for(re ll i=1;i<=e;++i)
#define r0 return 0;
#define e0 exit(0);
inline ll read(){
ll x=0,f=0;char ch=getchar();
while(ch>'9'||ch<'0')f|=ch=='-',ch=getchar();
while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?-x:x;
}
void print(int x)
{
if(x<0){putchar('-');x=-x;}
if(x>9)print(x/10);
putchar(x%10+'0');
}
inline ll Max(ll a,ll b){return a>b?a:b;}
inline ll Min(ll a,ll b){return a<b?a:b;}
inline ll power(ll base,ll p){
ll ans=1,tmp=base;
while(p!=0){
if(p&1)ans=(ans*tmp);
tmp=(tmp*tmp);p=p>>1;
}
return ans;
}
const int N=200001;
ll n,m,head[N],tot,dep[N],t;
ll f[N],fa[N][41],ww[N][41];
ll v[N]={0};
struct node{
ll to,next,w;
}e[N],best[N];
inline void add(ll u,ll v,ll w){
tot++;
best[tot].next=head[u];
best[tot].w=w;
head[u]=tot;
best[tot].to=v;
}
bool cmp(node a,node b){
return a.w>b.w;
}
inline ll find(ll x){
x==f[x]?x:f[x]=find(f[x]);
}
void dfs(ll num){
v[num]=1;
for(re ll i=head[num];i;i=best[i].next){
if(v[best[i].to])continue;
dep[best[i].to]=dep[num]+1;
fa[best[i].to][0]=num;
ww[best[i].to][0]=best[i].w;
dfs(best[i].to);
}
return;
}
inline ll lca(ll x,ll y){
if(find(x)!=find(y))return -1;
ll ans=999999999;
if(dep[x]>dep[y])swap(x,y);
for(re ll i=20;i>=0;--i){
if(dep[fa[y][i]]>=dep[x]){
ans=min(ans,ww[y][i]);
y=fa[y][i];
}
}
if(x==y)return ans;
for(re ll i=20;i>=0;--i){
if(fa[x][i]!=fa[y][i]){
ans=min(ans,min(ww[x][i],ww[y][i]));
x=fa[x][i];
y=fa[y][i];
}
ans=min(ans,min(ww[x][0],ww[y][0]));
return ans;
}
}
int main(){
n=read();m=read();
fo(i,m){
e[i].next=read();
e[i].to=read();
e[i].w=read();
}
sort(e+1,e+1+m,cmp);
fo(i,n)f[i]=i;
fo(i,m){
if(find(e[i].next)!=find(e[i].to)){
f[find(e[i].next)]=find(e[i].to);
add(e[i].next,e[i].to,e[i].w);
add(e[i].to,e[i].next,e[i].w);
}
}
fo(i,n){
if(!v[i]){
dep[i]=1;
dfs(i);
fa[i][0]=i;
ww[i][0]=999999999;
}
}
fo(i,20){
fo(j,n){
fa[j][i]=fa[fa[j][i-1]][i-1];
ww[j][i]=min(ww[j][i-1], ww[fa[j][i-1]][i-1]);
}
}
t=read();
while(t--){
ll x=read(),y=read();
printf("%lld\n",lca(x,y));
}
return 0;
}