随笔档案

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define inf (1<<29)
const int maxn = 10010 , maxm = 30030;
int n;
int dist1[maxn],dist2[maxn],dist3[maxn],p[maxn],node1[maxn],node2[maxn],d[maxn],pre[maxn];
struct Edge {
    int v,w,next;   
}edge[maxm];
int E,head[maxn];
void init() {
    E=0;
    p[1] = -1;
    for(int i=1;i<=n;i++) {
        dist1[i]=dist2[i]=dist3[i]=inf;
        d[i]=0;
        head[i]=-1;
        node1[i]=node2[i]=-1;
    }   
}
void addedge(int u,int v,int w) {
    edge[E].v=v;edge[E].w=w;edge[E].next=head[u];head[u]=E++;
    edge[E].v=u;edge[E].w=w;edge[E].next=head[v];head[v]=E++;   
}
int dfs1(int u) {
    if(d[u]==1 && u != 1) {
        node1[u] = u;
        dist1[u] = 0;
        return dist1[u];   
    }   
    for(int i=head[u];i!=-1;i=edge[i].next) {
        int v = edge[i].v , w = edge[i].w;
        if(v == p[u]) continue;
        p[v] = u;
        pre[v] = i;
        if(dfs1(v) + w < dist1[u]) {
            node1[u] = v;
            dist1[u] = dist1[v] + w;   
        }    
    }
    for(int i=head[u];i!=-1;i=edge[i].next) {
        int v = edge[i].v , w = edge[i].w;
        if(v == p[u] || v == node1[u]) continue;
        if(dist1[v] + w < dist2[u]) dist2[u] = dist1[v] + w;    
    }
    return dist1[u];
}
void dfs2(int u) {
    if(u == 1) {
        if(d[u] == 1) dist3[u] = 0;
        else dist3[u] = inf;
    }  
    else {
        if(u == node1[ p[u] ]) {
            dist3[u] = min(dist3[ p[u] ] , dist2[ p[u] ]) + edge[ pre[u] ].w;   
        }   
        else {
            dist3[u] = min(dist3[ p[u] ] , dist1[ p[u] ]) + edge[ pre[u] ].w;   
        }
    }
    for(int i=head[u];i!=-1;i=edge[i].next) {
        int v = edge[i].v;
        if(v == p[u]) continue;
        dfs2(v);   
    }
}
int main() {
    while(~scanf("%d",&n) && n) {
        init();
        for(int i=1;i<n;i++) {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);   
            d[u] ++; d[v] ++;
        }
        dfs1(1);
        dfs2(1);
        int ans = inf;
        for(int i=1;i<=n;i++) {
            if(dist1[i] + dist2[i] < ans) ans = dist1[i] + dist2[i];
            if(dist1[i] + dist3[i] < ans) ans = dist1[i] + dist3[i];   
        }   
        printf("%d\n",ans);
    }
    return 0;   
}