旅行[板子题]

链接：https://ac.nowcoder.com/acm/contest/50380/D
来源：牛客网

小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

AC代码:

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
typedef pair<int,int> PII;

int t;
int n, m;
int h[N], e[2 * N], ne[2 * N], w[2 * N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dij(int x) {
	int max1 = 0, max2 = 0;
	memset(dist, 0x3f, sizeof dist);
	dist[x] = 0;
	priority_queue<PII, vector<PII>, greater<PII>> heap; //小根堆的语法,请熟记
	heap.push({0, x});
	while (heap.size()) {
		auto t = heap.top();
		heap.pop();
		int ver = t.second, dis = t.first;
		if (st[ver]) continue;
		max2 = max(max2, dist[ver]);
		st[ver] = true;
		for (int i = h[ver]; i != -1; i = ne[i]) {
			int j = e[i];
			if (dist[j] > dis + w[i]) {
				//我认为写个dist[j]>dist[ver]+w[i];也是可以的
				dist[j] = dis + w[i];
				heap.push({dist[j], j});
			}
		}
		if (max1 < max2) swap(max1, max2);
	}
	for (int i = 1; i <= n; i ++ ) st[i] = false;//因为st是全局数组, 所以一定要还原现场
	if (max2 == 0) return -1;
	else return max1 + max2;
}

void solved() {
	scanf("%d%d", &n, &m);
	memset(h, -1,sizeof h);
	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 ++ )
		ans = max(ans, dij(i));
	printf("%d\n",ans);
	idx = 0;//还原idx数组!!
	return ;
}

int main() {
	scanf("%d",&t);
	while (t -- )
		solved();
	return 0;
}
/*
  1
  7 7
  1 2 100
  2 3 100
  1 4 4
  4 5 6
  5 6 10
  1 6 4
  6 7 8
 */