C++14(g++5.4) 解法, 执行用时: 385ms, 内存消耗: 688K, 提交时间: 2020-08-23 13:01:03

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
vector<pii> e[1005];
int dis[1005],n,m;
queue<int> q;
int Dijkstra(int x)
{
    int i,len;
    memset(dis,0x3f3f3f,sizeof(dis));
    dis[x]=0;
    q.push(x);
    while(!q.empty())
    {
        int d=q.front();
        q.pop();
        len=e[d].size();
        for(i=0;i<len;i++)
            if(dis[e[d][i].first]>dis[d]+e[d][i].second)
            {
                dis[e[d][i].first]=dis[d]+e[d][i].second;
                q.push(e[d][i].first);
            }
    }
    sort(dis+1,dis+1+n);
    for(i=1;i<=n;i++)
        if(dis[i]>=0x3f3f3f)
            break;
    if(i>=4)
        return (dis[i-2]+dis[i-1]);
    else
        return -1;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int from,to,c,i,sum=-1;
        cin>>n>>m;
        for(int i=1;i<=1000;i++)e[i].clear();
        for(i=1;i<=m;i++)
        {
            scanf("%d %d %d",&from,&to,&c);
            e[from].push_back(make_pair(to,c));
            e[to].push_back(make_pair(from,c));
        }
        for(i=1;i<=n;i++)
            sum=max(sum,Dijkstra(i));
        cout<<sum<<endl;
    }
}

C++(clang++ 11.0.1) 解法, 执行用时: 573ms, 内存消耗: 2220K, 提交时间: 2022-08-04 10:15:34

#include<bits/stdc++.h>
using namespace std;
const int N=120010;
int h[N],e[N],ne[N],w[N],idex,n,m,t,dist[N],res=-1;
bool st[N];
void add(int a,int b,int c){
	e[idex]=b;
	ne[idex]=h[a];
	w[idex]=c;
	h[a]=idex++;
}
void spfa(int s){
	memset(dist,0x3f,sizeof(dist));
	memset(st,false ,sizeof(st));
	queue<int>q;
	q.push(s);
	dist[s]=0;
	st[s]=true;
	while(!q.empty()){
		int pos=q.front();
		q.pop();
		st[pos]=false;
		for(int i=h[pos];i!=-1;i=ne[i]){
			if(dist[e[i]]>dist[pos]+w[i]){
				dist[e[i]]=dist[pos]+w[i];
				if(!st[e[i]]){
					st[e[i]]=true;
					q.push(e[i]);
				}
			}
		}
	}
	int cnt[N];
	cnt[0]=0;
	for(int i=1;i<=n;i++)if(dist[i]!=0x3f3f3f3f)cnt[++cnt[0]]=dist[i];
	if(cnt[0]>2){
		sort(cnt+1,cnt+cnt[0]+1);
		res=max(res,cnt[cnt[0]]+cnt[cnt[0]-1]);
	}
}
int main(){
	cin>>t;
	while(t--){
		res=-1;
		memset(h,-1,sizeof(h));
		memset(ne,-1,sizeof(ne));
		int a,b,c;
		scanf("%d%d",&n,&m);
		while(m--){
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,c);
			add(b,a,c);
		}
		for(int i=1;i<=n;i++)spfa(i);
		printf("%d\n",res);
	}
}