Beta Round #57-D: Eternal Victory

keyword

木　C++

問題概要

ノード数V(<10^5)の重み付き木が与えられる。ノード0から全てのノードを訪ねたい。最後のノードを訪ねるまでの総距離を最小化する問題。

解法

基本的にどの辺も2度通る。例外的に始点から終点までの辺は1回だけで良い。なので終点までの辺の長さが最も長くなるように終点を選べば良い。

const int MAX_N = 100009;
vector< pair<int,int> > vs[MAX_N];
bool visited[MAX_N];
int64 dist[MAX_N];
int N;

void dfs(int v){
    int64 ans = 0;
    visited[v] = true;
    for(int i=0; i<vs[v].size(); i++){
        int u = vs[v][i].first;
        if(!visited[u]){
            dist[u] = dist[v] + vs[v][i].second;
            dfs(u);
        }
    }
}

int main(){
    scanf("%d",&N);
    int64 ans = 0;
    for(int i=0; i<N-1; i++){
        int x, y, w;
        scanf("%d%d%d",&x,&y,&w);
        ans += w;
        x--;y--;
        vs[x].push_back( MP(y,w) );
        vs[y].push_back( MP(x,w) );
    }
    ans *= 2;
    dfs(0);
    cout << ans - (*max_element(dist,dist+N)) << endl;
    return 0;
}