描述

有N个城市，请你从这N个城市中选择出3个城市，做为起点、终点和购物点，你需要做到这3个城市的路途最远，这样你可以沿途欣赏风景，但是导游希望这3个城市的距离最短，请你帮导游计算下满足自己和导游要求下，3个城市最短距离是多少？

输入

本题包含多组输入，第一行输入一个整数t，表示测试数据的组数 每组测试数据第一行输入两个数N,M表示一共有N城市，以及城市间路的数量。 接下来M行，每行三个数，a，b，c表示从a城市和b城市之间有一条长为c的路 t<=40 3<=N,M<=1000 1<=a,b<=N 1<=c<=100

输出

每组数据输出两行， 每组数据包含一行，输出一个数，表示整条路程的路长。 如果找不到可行解，输出-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;
struct node{
	int v,w;
	bool operator<(const node &x)const{
		return w > x.w;
	}
};
vector<node>e[200002];
int n,m,s;
int dis[200002];
bool vis[200002];
int t,a,b,c;
void dijkstra(int s){
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	priority_queue<node>q;
	dis[s]=0;
	q.push({s,0});
	while(!q.empty()){
		int u=q.top().w;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i].v;
			int w=e[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push({v,dis[v]});
			}
		}
	}
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>m;
		for(int i=1;i<=m;i++){
			cin>>a>>b>>c;
			e[a].push_back({b,c});
			e[b].push_back({a,c});
		}
		int m1=-1,m2=-1;
		int ans=-1;
		for(int i=1;i<=n;i++){  
			dijkstra(i);
			for(int j=1;j<=n;j++){
				if(dis[j]>=m1&&dis[j]!=0x3f3f3f3f){
					m2=m1;
					m1=dis[j];
				}
				if(dis[j]>=m2&&dis[j]<m1&&dis[j]!=0x3f3f3f3f){
					m2=dis[j];
				}
			}
			ans=max(ans,m1+m2);	
		}
		if(ans==2*0x3f3f3f3f) cout<<"-1"<<endl;
		else cout<<ans<<endl;
		for(int i=1;i<=n;i++) e[i].clear();
	}	
	return 0;
}

样例没过，差一些，编译时还会警告