思路: 该题其实质让求无根树上两个最近叶节点之间的距离; 问题转化为 1在有根树(任选一节点做根,作者选的是一个叶节点)上先求从每个节点出发到leaf的最短距离,然后
对于每个至少有两个子结点的结点选出最小的两个距离更新结果;
#include <vector> #include <cstdio> #include <cstring> #include <iostream> #define INF 10000000 using namespace std; typedef long long LL; const int maxn = 10000 + 10; struct node{ int to,len,cun; node(int x=0,int y=0):to(x),len(y){} }; vector<node> G[maxn]; void init(int n){ for(int i=1;i<=n;i++) G[i].clear(); } int ans; int dfs(int u,int fa) { if(G[u].size()==1){ if(G[u][0].to==fa) return 0; else{ return G[u][0].len+dfs(G[u][0].to,u); } } if(G[u].size()==2){ int t=(G[u][0].to==fa ? 1:0); return G[u][t].len+dfs(G[u][t].to,u); } int min_=INF; for(int i=0;i<G[u].size();i++){ int v=G[u][i].to,len=G[u][i].len; if(v!=fa){ G[u][i].cun=len+dfs(v,u); min_=min(min_,G[u][i].cun); } } for(int i=0;i<G[u].size();i++) for(int j=i+1;j<G[u].size();j++)if(G[u][i].to!=fa&&G[u][j].to!=fa){ ans=min(ans,G[u][i].cun+G[u][j].cun); } return min_; } int main() { int n; while(scanf("%d",&n)==1&&n){ init(n); for(int i=1;i<n;i++){ int x,y,z; scanf("%d %d %d",&x,&y,&z); G[x].push_back(node(y,z)); G[y].push_back(node(x,z)); } ans=INF; for(int i=1;i<=n;i++) if(G[i].size()==1){ ans=min(ans,dfs(i,-1)); break; } printf("%d\n",ans); } return 0; }