NC14550 旅行
题意：
选择三个点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);
}
} 
投递传音控股等公司10个岗位 >
