题目描述
小z放假了，准备到RRR城市旅行，其中这个城市有N个旅游景点。小z时间有限，只能在三个旅行景点进行游玩。小明租了辆车，司机很善良，说咱不计路程，只要你一次性缴费足够，我就带你走遍RRR城。
小z很开心，直接就把钱一次性缴足了。然而小z心机很重，他想选择的路程尽量长。
然而司机也很聪明，他每次从一个点走到另外一个点的时候都走最短路径。
你能帮帮小z吗？
需要保证这三个旅行景点一个作为起点，一个作为中转点一个作为终点。（一共三个景点，并且需要保证这三个景点不能重复）.
输入描述:
本题包含多组输入，第一行输入一个整数t，表示测试数据的组数
每组测试数据第一行输入两个数N,M表示RRR城一共有的旅游景点的数量，以及RRR城中有的路的数量。
接下来M行，每行三个数，a，b，c表示从a景点和b景点之间有一条长为c的路
t<=40
3<=N,M<=1000
1<=a,b<=N
1<=c<=100
输出描述:
每组数据输出两行，
每组数据包含一行，输出一个数，表示整条路程的路长。
如果找不到可行解，输出-1.
示例1
输入
4
7 7
1 2 100
2 3 100
1 4 4
4 5 6
5 6 10
1 6 4
6 7 8
7 3
1 2 1
1 3 1
1 3 2
7 3
1 2 1
3 4 1
5 6 1
8 9
1 2 1
2 3 1
3 4 1
4 1 1
4 5 1
5 6 1
6 7 1
7 8 1
8 5 1
输出
422
3
-1
9
题解
枚举，最短路。
枚举中转站，以中转站为起点求最短路，找两个距离最远的，更新答案。
#include <bits/stdc++.h>
using namespace std; const int maxn = 2000 + 10;
int T, n, m;
int h[maxn];
int to[maxn];
int val[maxn];
int nx[maxn];
int dis[maxn];
int f[maxn];
int sz; void add(int a, int b, int c) {
to[sz] = b;
val[sz] = c;
nx[sz] = h[a];
h[a] = sz ++;
} void spfa(int x) {
for(int i = 1; i <= n; i ++) {
dis[i] = 500000;
f[i] = 0;
}
queue<int> q;
q.push(x);
f[x] = 1;
dis[x] = 0;
while(!q.empty()) {
int id = q.front();
q.pop();
f[id] = 0;
for(int i = h[id]; i != -1; i = nx[i]) {
if(dis[id] + val[i] < dis[to[i]]) {
dis[to[i]] = dis[id] + val[i];
if(f[to[i]] == 0) {
f[to[i]] = 1;
q.push(to[i]);
}
}
}
}
} int main() {
scanf("%d", &T);
while(T --) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) {
h[i] = -1;
}
sz = 0;
while(m --) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
int ans = -1;
for(int i = 1; i <= n; i ++) {
spfa(i);
sort(dis + 1, dis + 1 + n);
int sum1 = 0;
int sum2 = 0;
for(int j = n; j >= 1; j --) {
if(dis[j] == 0) continue;
if(dis[j] == 500000) continue;
if(sum1 < 2) {
sum1 ++;
sum2 = sum2 + dis[j];
}
}
if(sum1 == 2) {
ans = max(ans, sum2);
}
}
printf("%d\n", ans);
}
return 0;
}