Codeforces Solution-D. Eternal Victory-Solution in C, C++, Java, Python

3
1 2 3
2 3 4

7

3
1 2 3
1 3 3

9

#1 Code Example with C++ Programming

Code - C++ Programming

#include <cstdio>
#include <iostream>
#include <vector>


void dfs(int64_t node, const std::vector<std::vector<std::pair<int64_t, int64_t> > > &g, std::vector<bool> &visited, std::vector<int64_t> &distance){

    if(visited[node]){return;}
    visited[node] = 1;

    for(int64_t p = 0; p < g[node].size(); p++){
        int64_t u = g[node][p].first;
        if(visited[u]){continue;}
        distance[u] = distance[node] + g[node][p].second;
        dfs(u, g, visited, distance);
    }

    return;
}


int main(){

    int64_t n; scanf("%lld", &n);
    std::vector<std::vector<std::pair<int64_t, int64_t> > > g(n);
    int64_t total(0);
    for(int64_t p = 1; p < n; p++){
        int64_t x, y, d; scanf("%lld %lld %lld", &x, &y, &d);
        --x; --y;
        g[x].push_back(std::make_pair(y, d));
        g[y].push_back(std::make_pair(x, d));
        total += 2 * d;
    }

    std::vector<bool> mark(n, 0);
    std::vector<int64_t> dist(n, 0);
    dfs(0, g, mark, dist);
    int64_t maxDist(0);
    for(int64_t p = 0; p < n; p++){maxDist = (maxDist > dist[p]) ? maxDist : dist[p];} 
    printf("%lld\n", total - maxDist);

    return 0;
}

Copy The Code & Try With Live Editor

Input

Output