在某个遥远的国家里，有 n个城市。编号为 1,2,3,…,n。这个国家的政府修建了m 条双向道路，每条道路连接着两个城市。政府规定从城市 S 到城市T需要收取的过路费为所经过城市之间道路长度的最大值。如：A到B长度为 2，B到C 长度为3，那么开车从 A经过 B到C 需要上交的过路费为 3。
佳佳是个做生意的人，需要经常开车从任意一个城市到另外一个城市，因此他需要频繁地上交过路费，由于忙于做生意，所以他无时间来寻找交过路费最低的行驶路线。然而， 当他交的过路费越多他的心情就变得越糟糕。 作为秘书的你，需要每次根据老板的起止城市，提供给他从开始城市到达目的城市，最少需要上交多少过路费。

    第一行是两个整数 n 和m，分别表示城市的个数以及道路的条数。
接下来 m 行，每行包含三个整数 a，b，w（1≤a，b≤n，0≤w≤10^9），表示a与b之间有一条长度为 w的道路。
接着有一行为一个整数 q，表示佳佳发出的询问个数。
再接下来 q行，每一行包含两个整数 S，T（1≤S,T≤n，S≠T）, 表示开始城市S 和目的城市T。

    输出共q行，每行一个整数，分别表示每个询问需要上交的最少过路费用。输入数据保证所有的城市都是连通的。

4 5
1 2 10
1 3 20
1 4 100
2 4 30
3 4 10
2
1 4
4 1

20
20

对于 30%的数据，满足 1≤ n≤1000，1≤m≤10000，1≤q≤100；
对于 50%的数据，满足 1≤ n≤10000，1≤m≤10000，1≤q≤10000；
对于 100%的数据，满足 1≤ n≤10000，1≤m≤100000，1≤q≤10000；

题解：

类似货车运输

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int first[233333], next[433333], tot = 0;
int fa[233333], sd[233333], t[233333][30];
int d[233333][30];
struct edge
{
	int from, to, cost;
}es[433333];
struct love
{
	int from, to, cost;
}xl[433333];
bool cmp(edge a, edge b)
{
	return a.cost < b.cost;
}
void build(int f, int t, int dd)
{
	xl[++tot] = (love){f, t, dd};
	next[tot] = first[f];
	first[f] = tot;
}
int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void dfs(int x)
{
	int v;
	for (int i = first[x]; i != -1; i = next[i])
	{
		v = xl[i].to;
		if (!sd[v])
		{
			t[v][0] = x;
			d[v][0] = xl[i].cost;
			for (int j = 1; j <= 20; j++)
			{
				d[v][j] = max(d[v][j-1], d[t[v][j-1]][j-1]);
				t[v][j] = t[t[v][j-1]][j-1];
			}
			sd[v] = sd[x] + 1;
			dfs(v);
		}
	}
}
int lca(int u, int v)
{
	int ans = 0;
	if (sd[u] < sd[v])
		swap(u, v);
	int i, j;
	for (i = 0; (1 << i) <= sd[u]; i++);
	i--;
	for (j = i; j >= 0; j--)
		if (sd[u] - (1 << j) >= sd[v])
		{
			ans = max(ans, d[u][j]);
			u = t[u][j];
		}
	if (u == v)
		return ans;
	for (j = i; j >= 0; j--)
	{
		//cout<<"ha";
		if (t[u][j] != -1 && t[u][j] != t[v][j])
		{
			ans = max(ans, d[u][j]);
			ans = max(ans, d[v][j]);
			u = t[u][j];
			v = t[v][j];
		}
	}
	if (u != v)
	{
		ans = max(ans, d[u][0]);
		ans = max(ans, d[v][0]);
	}
	return ans;
}
int main()
{
	memset(first, -1, sizeof(first));
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		scanf("%d%d%d", &es[i].from, &es[i].to, &es[i].cost);
	sort(es + 1, es + m + 1, cmp);
	for (int i = 1; i <= n; i++)
		fa[i] = i;
	for (int i = 1; i <= m; i++)
	{
		int x = es[i].from, y = es[i].to;
		if (find(x) != find(y))
		{
			fa[find(x)] = find(y);
			build(x, y, es[i].cost);
			build(y, x, es[i].cost);
		}
	}
	sd[1] = 1;
	dfs(1);
	int q;
	cin >> q;
	for (int i = 1; i <= q; i++)
	{
		int ss, tt;
		scanf("%d%d", &ss, &tt);
		printf("%d\n", lca(ss, tt));
	}
	return 0;
}