C++(g++ 7.5.0) 解法, 执行用时: 445ms, 内存消耗: 668K, 提交时间: 2022-11-30 16:11:39

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
typedef pair<int ,int > PII;
const int N=2010;
int dis[N];
bool vis[N];
int n,m;
vector<PII> g[N];
int solve(int s){
	priority_queue<PII ,vector<PII>,greater<PII> > q;
	memset(vis,false,sizeof vis);
	memset(dis,0x3f,sizeof dis);
	q.push({0,s});
	dis[s]=0;
	int ans1=0,ans2=0;
	while(q.size()){
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=true;
		ans2=max(ans2,dis[u]);
		if(ans2>ans1)swap(ans1,ans2);
		for(int i=0;i<g[u].size();i++){
			int x=g[u][i].first,y=g[u][i].second;
			if(dis[x]>dis[u]+y){
				dis[x]=dis[u]+y;
				q.push({dis[x],x});
			}
		}
	} 
	if(ans2==0)return 0;
	return (ans1+ans2);
}
int main()
{
	int t;
	cin>>t;
	while(t--){
		cin>>n>>m;
		for(int i=1;i<=n;i++)g[i].clear();
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			g[u].push_back({v,w});
			g[v].push_back({u,w});
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			ans=max(ans,solve(i));
		}
		if(ans)cout<<ans<<endl;
		else cout<<-1<<endl;
	}
	return 0;
}

C++ 解法, 执行用时: 475ms, 内存消耗: 556K, 提交时间: 2022-03-15 19:24:26

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1010;
int n,m;
int dis[N],vis[N];
vector<PII> G[N];
int ans;
int dij(int s){
	priority_queue<PII,vector<PII>,greater<PII> > q;
	memset(vis,0,sizeof vis);
	memset(dis,0x3f,sizeof dis);
	q.push({0,s});
	dis[s]=0;
	int res1=0,res2=0;
	while(q.size()){
		int u=q.top().second;q.pop();
		if(vis[u])continue;
		vis[u]=1;
		res2=max(res2,dis[u]);
		if(res2>res1)swap(res2,res1);
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].first,d=G[u][i].second;
			if(dis[v]>dis[u]+d){
				dis[v]=dis[u]+d;
				q.push({dis[v],v});
			}
		}
	}
	if(res2==0) return 0;
	return (res1+res2);
}

int main(){
	int T;
	cin>>T;
	while(T--){
		for(int i=1;i<=n;i++)G[i].clear();
		cin>>n>>m;
		ans=-1;
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			G[u].push_back({v,w});
			G[v].push_back({u,w});
		}
		for(int i=1;i<=n;i++){
			ans=max(ans,dij(i));
		}
		if(ans==0)ans=-1;
		cout<<ans<<endl;
	}
}