题解

由于每个城市都得运送货物，所以如果最后返回首都的话总路径长度为“两倍的所有道路长度”；但是题目说明了最后可以不返回首都，这就使得有一条从根节点开始的路径不用*2，希望路径最短，所以这条不用*2的路径应该是从根节点开始的最长路径。

代码思路：

1. 构造树，同时统计所有道路长度总和的2倍。
2. 递归寻找从根节点开始的最长路径。
3. 用2倍的所有道路长度总和-最长路径，即为所求。

#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+5;

struct Node{
	long long l,k;
};

long long n,sum,nmax;
bool vis[N];
vector<Node> u[N];

void dfs(long long x,long long now){
	if(vis[x]) return;
	vis[x]=1;
	
	nmax=max(nmax,now);
	
	for(auto i:u[x]){
		dfs(i.k,now+i.l);
	}
}

int main(){
	cin>>n;
	for(long long i=1;i<n;i++){
		long long x,y,z;
		
		cin>>x>>y>>z;
		
		u[x].push_back({z,y});
		u[y].push_back({z,x});
		sum+=2*z;
	}
	
	dfs(1,0);
	
	cout<<sum-nmax;
	
	return 0;
}