题目描述

给定一个包含 n 个节点和 m 条边的图，每条边有一个权值。 你的任务是回答 k 个询问，每个询问包含两个正整数 s 和 t 表示起点和终点，要求寻找从 s 到 t 的一条路径，使得路径上权值最大的一条边权值最小。

输入格式

第一行包含三个整数 n、m、k，分别表示 n 个节点， m 条路径， k 个询问。

接下来 m 行，每行三个整数 u, v, w, 表示一个由 u 到 v 的长度为 w 的双向边。

再接下来 k 行，每行两个整数 s, t，表示询问从 s 连接到 t 的所有路径中单边长度最大值的最小值。

输出格式

输出包含 k 行，每一行包含一个整数 p。p 表示 s 连接到 t 的所有路径中单边长度最大值的最小值。另外，如果 s 到 t 没有路径相连通，输出 -1 即可。

样例输入

8 11 3  1 2 10  2 5 50  3 4 60  7 5 60  3 6 30  1 5 30  6 7 20  1 7 70  2 3 20  3 5 40  2 6 90  1 7  2 8  6 2

样例输出

30  -1  30

数据范围与提示

对于 30% 的数据 n≤ ≤ 100,m≤ ≤ 1000,k≤ ≤ 100,w≤ ≤ 1000

对于 70% 的数据 n≤ ≤ 1000,m≤ ≤ 10000,k≤ ≤ 1000,w≤ ≤ 100000

对于 100% 的数据 n≤ ≤ 1000,m≤ ≤ 100000,k≤ ≤ 1000,w≤ ≤ 10000000

本题可能会有重边。 为了避免 Special Judge，本题所有的 w 均不相同。

---

 

根据常识可得“从 s 连接到 t 的所有路径中单边长度最大值要最小”，那么他们走过的边肯定在当前图的最小生成树里

1.求出最小生成树，建新图

2.求一棵树里两点关系->LCA

3.在求最小生成树时,我用了并查集维护连通性-》在后面询问时来判断两点是否在同一连通块里

#include
     
      #define re return#define lowbit(x) (x&(-x))#define dec(i,l,r) for(int i=l;i>=r;--i) #define inc(i,l,r) for(int i=l;i<=r;++i)const int maxn=1005,maxm=200005;using namespace std;template
      
       inline void rd(T&x){	char c;bool f=0;	while((c=getchar())<'0'||c>'9')if(c=='-')f=1;	x=c^48;	while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);	if(f)x=-x;} int n,m,q,deep[maxn],hd[maxn],fa[maxn],f[maxn][25],dis[maxn][25];struct node{	int fr,to,nt,val;	bool operator<(node x)const 	{		re val
       
        =deep[y])	{		ans=max(ans,dis[x][i]);		x=f[x][i];	}	if(x==y)re ans;		dec(i,24,0)	if(f[x][i]!=f[y][i]) 	{		ans=max(ans,dis[x][i]);		ans=max(ans,dis[y][i]);		x=f[x][i];		y=f[y][i];	}	re max(ans,max(dis[x][0],dis[y][0]));}int main(){	int x,y,z;	rd(n),rd(m);rd(q);	inc(i,1,m)	{		rd(x),rd(y),rd(z);		e1[i]=(node){x,y,0,z}; 	}		sort(e1+1,e1+m+1);		int cnt=0,k=0;	inc(i,1,n)fa[i]=i;	inc(i,1,m)	{		int x=e1[i].fr,y=e1[i].to,w=e1[i].val;		int f1=find(fa[x]),f2=find(fa[y]); 		if(f1!=f2)		{			e[++k]=(node){x,y,hd[x],w};hd[x]=k;			e[++k]=(node){y,x,hd[y],w};hd[y]=k;			++cnt;			fa[f1]=f2;			if(cnt==n-1)break;		} 	}		inc(i,1,n)	if(!deep[i])dfs(i,0);	int s,t;	inc(i,1,q)	{		rd(s),rd(t);		if(i==27)		x=1;		if(find(s)!=find(t))printf("-1\n");		else printf("%d\n",LCA(s,t));	}	re 0;}