因为可能成环，这样可能导致到达点的最小权值不一，所以用最小生成树的方法重新建图
然后我是利用倍增的思想建立从i点开始，到上面点的距离ff和最小权值ww
因为最小权值不好直接建立，所以不如最后统一建立
最后就是寻找最近公共祖先的模板了
一组hack：
cin
5 4
1 2 1
1 3 1
2 3 1
4 5 5
1
4 5
cout
5
注意这组数据，也就是说数据可能是森林，要遍历完所以数据，当时跳进坑了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, m;
//链式前向星
int h[N], ne[N * 2], w[N * 2], to[N * 2],cnt;
void add(int a, int b,int c) {
to[++cnt] = b;
ne[cnt] = h[a];
w[cnt] = c;
h[a] = cnt;
}
//Kruskal最小生成树，改为最大
struct edge {
int u, v, w;
bool operator<(const edge& a)const {
return w>a.w;
}
}e[N];
int f[N];
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
void Kruskal() {
sort(e + 1, e + 1 + m);
for (int i = 1; i <= n; i++) f[i] =i;
for (int i = 1; i <= m; i++) {
int x = find(e[i].u);
int y = find(e[i].v);
if (x != y) {
f[x] = y;
add(e[i].u, e[i].v, e[i].w);
add(e[i].v, e[i].u, e[i].w);
}
}
}
//先遍历一遍，找好跳一个点的距离和权值
int ff[N][22], ww[N][22],dep[N],vis[N];
void dfs(int u, int father) {
vis[u] = 1;
dep[u] = dep[father] + 1;
ff[u][0] = father;
for (int i = h[u]; i; i = ne[i]) {
int v = to[i];
if (v == father) continue;
ww[v][0] = w[i];
dfs(v, u);
}
}
//最近公共祖先模板
int lca(int u, int v) {
if (find(u) != find(v)) return -1;
if (dep[u] < dep[v]) swap(u, v);
int ans = 1e9;//初始化无穷
for (int i = 19; i >= 0; i--) {
if (dep[ff[u][i]]>= dep[v]) {
ans = min(ans, ww[u][i]);//维护最小
u = ff[u][i];
}
}
if (v == u) return ans;//相遇直接返回
for (int i = 19; i >= 0; i--) {
if (ff[u][i] != ff[v][i]) {
ans = min(ans, min(ww[u][i], ww[v][i]));//维护最小
u = ff[u][i]; v = ff[v][i];
}
}
return min(ans, min(ww[u][0], ww[v][0]));//维护最小
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
e[i] = { x,y,z };
}
Kruskal();
for (int i = 1; i <= n; i++) {//全部遍历
if (!vis[i]) {
dfs(i, 0);
}
}
for (int i = 1; i <= 19; i++) {//统一计算
for (int j = 1; j <= n; j++) {
ff[j][i] = ff[ff[j][i - 1]][i - 1];
ww[j][i] = min(ww[ff[j][i - 1]][i - 1], ww[j][i - 1]);
}
}
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
cout << lca(x, y) << '\n';
}
}