题意：

选择三个点a,b,c，求a走到b，b走到c的距离的最大值
n<=1000，m<=1000

做法：

由于 n=1000，所以我们考虑枚举中间点 b，然后求出以 b 为起点，到其他点的距离，然后找到两个距离 b 最远的点，更新答案即可，时间复杂度 O(n^2*logn) 
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e3 + 5;
struct edge
{
	int to;
	ll w;
	int nex;
}e[MAXN * 2];
int head[MAXN], tot;
bool book[MAXN];
ll dis[MAXN];
void init(int n)
{
	fill(head, head + n + 1, -1);
	tot = 1;
}
void add(int a, int b, ll c)
{
	e[tot] = edge{ b,c,head[a] };
	head[a] = tot++;
}
#define Pair pair<ll,int>
void dij(int st)
{
	priority_queue<Pair, vector<Pair>, greater<Pair> >q;
	q.push(Pair{ 0,st });
	while (!q.empty())
	{
		int u = q.top().second;
		q.pop();
		if (book[u])
			continue;
		book[u] = true;
		for (int i = head[u]; i + 1; i = e[i].nex)
		{
			int v = e[i].to;
			if (dis[v] > dis[u] + e[i].w)
			{
				dis[v] = dis[u] + e[i].w;
				q.push(Pair{ dis[v],v });
			}
		}
	}
}
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		int n, m;
		sc("%d%d", &n, &m);
		init(n);
		for (int i = 0; i < m; i++)
		{
			int a, b; ll c;
			sc("%d%d%lld", &a, &b, &c);
			add(a, b, c);
			add(b, a, c);
		}
		ll ans = 0;
		for (int i = 1; i <= n; i++)
		{
			fill(dis, dis + n + 1, 1e18);
			fill(book, book + n + 1, false);
			dis[i] = 0;
			dij(i);
			ll ans1 = 0, ans2 = 0;
			for (int j = 1; j <= n; j++)
			{
				if (j != i && dis[j] != 1e18)
				{
					if (dis[j] > ans1)
					{
						ans2 = ans1;
						ans1 = dis[j];
					}
					else if (dis[j] > ans2)
						ans2 = dis[j];
				}
			}
			if (ans2 != 0)
				ans = max(ans, ans1 + ans2);
		}
		if (ans == 0)
			ans = -1;
		pr("%lld\n", ans);
	}
}