传送门

思路

首先建图，题目有重边，可建一棵最大生成树。给出的n有1e4，用floyd算法时间复杂度为n^3, 空间复杂度为n^2.因此需要用lca和树上倍增dp来做，如果询问的x，y不在一棵树上就输出-1，否则就跑个lca.

#代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
#define maxn 100005
#define mod 998244353
struct Edge{
    int to,next,w;
}edge[maxn];
struct e{
    int u,v,w;
}edge1[maxn];
int cnt,head[maxn],w[maxn][21],fa[maxn],f[maxn][21],n,m,dep[maxn];
void add_edge(int u,int v,int w){
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;
    edge[cnt].w=w;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
bool cmp(e a,e b){
    return a.w>b.w;
}
void init(){
    cnt=0; 
    for(int i=0;i<=n;i++){
		head[i]=-1,fa[i]=i;
	} 
}
int find(int x){
    return fa[x]==x?x:(fa[x]=find(fa[x]));
}
int lca(int x,int y){
    int i,ans=inf;
    if(dep[x]>dep[y]) swap(x,y);
    for(i=20;i>=0;i--){
        if(dep[f[y][i]]>=dep[x]) ans=min(ans,w[y][i]),y=f[y][i];
        if(x==y) return ans;
    }
    for(i=20;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            ans=min(ans,min(w[x][i],w[y][i]));
            x=f[x][i],y=f[y][i];
        }
    }
    return min(ans,min(w[x][0],w[y][0]));
}
void build(){
    for(int i=1;i<=m;i++){
        int u=edge1[i].u,v=edge1[i].v;
        int fu=find(u),fv=find(v);
        if(fu==fv) continue;
        add_edge(u,v,edge1[i].w);
        fa[fv]=fu;
    }
}
void dfs(int x){
    int i,j;
    for(i=head[x];i!=-1;i=edge[i].next){
        int v=edge[i].to,ww=edge[i].w;
        if(dep[v]) continue;
        dep[v]=dep[x]+1;
		w[v][0]=ww;
		f[v][0]=x;
        for(j=1;(1<<j)<dep[v];j++) f[v][j]=f[f[v][j-1]][j-1],w[v][j]=min(w[v][j-1],w[f[v][j-1]][j-1]);
        dfs(v);
    }
}

int main(){
    int i, j, k, t;
    scanf("%d%d",&n,&m);
    int u, v;
    init();
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&edge1[i].u,&edge1[i].v,&edge1[i].w);
    sort(edge1+1,edge1+m+1,cmp);
    build();
    for(i=1;i<=n;i++){
        if(dep[i]) continue;
        dep[i]=1;
        dfs(i);
    }
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&u,&v);
        if(find(u)!=find(v)){
            printf("-1\n");
            continue;
        }
        printf("%d\n",lca(u,v));
    }
}