C++11(clang++ 3.9) 解法, 执行用时: 1970ms, 内存消耗: 1384K, 提交时间: 2020-03-28 17:43:32

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+100;

int x[N],y[N],w[N];

vector<pair<int,int> >G[N]; 

int dp1[N],dp2[N];
int dis,res; 
void dfs1(int x,int fa)//直径 
{
	for(auto p:G[x])
	{
		int v=p.first,w=p.second;
		if(v==fa) continue;
		dfs1(v,x);
		if(dp1[x]<dp1[v]+w)
		{
			dp2[x]=dp1[x];
			dp1[x]=dp1[v]+w;
		}
		else if(dp2[x]<dp1[v]+w)dp2[x]=dp1[v]+w;
	}
	dis=max(dis,dp1[x]+dp2[x]);
}
void dfs2(int x,int fa,int ff)//算半径 
{
	res=min(res,max(ff,dp1[x]));
	for(auto p:G[x])
	{
		int v=p.first,w=p.second;
		if(v==fa) continue;
		if(dp1[x]==dp1[v]+w) dfs2(v,x,max(ff,dp2[x])+w);
		else dfs2(v,x,max(ff,dp1[x])+w);
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		cin>>x[i]>>y[i]>>w[i];
		G[x[i]].push_back(make_pair(y[i],w[i]));
		G[y[i]].push_back(make_pair(x[i],w[i]));
	}
	int ans=1e9;
	for(int i=1;i<n;i++)
	{
		memset(dp1,0,sizeof dp1);
		memset(dp2,0,sizeof dp2);
		dis=0,res=1e9;
		int d1,d2,r1,r2;
		dfs1(x[i],y[i]); d1=dis;dis=0;
		dfs2(x[i],y[i],0);r1=res;res=1e9;
		dfs1(y[i],x[i]); d2=dis;
		dfs2(y[i],x[i],0);r2=res;
		ans=min(ans,max(d1,max(d2,r1+r2+w[i])));
	}
	cout<<ans<<endl;
	return 0;
}