fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define go ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
  4. using namespace std;
  5.  
  6. int const N = 2e5 + 10;
  7. int const INF = 1e5;
  8. int n;
  9. vector<pair<int, int>> adj[N];
  10. long long dis[N];
  11. bool visited[N];
  12. void dfs(int s, long long w)
  13. {
  14.     visited[s] = true;
  15.     dis[s] = w;
  16.     for (auto i : adj[s])
  17.     {
  18.         if (!visited[i.first])
  19.             dfs(i.first, w + i.second);
  20.     }
  21. }
  22. void solve()
  23. {
  24.     cin >> n;
  25.     long long ans = 0;
  26.     for (int i = 1; i < n; i++)
  27.     {
  28.         int u, v, w;
  29.         cin >> u >> v >> w;
  30.         adj[u].push_back({v, w});
  31.         adj[v].push_back({u, w});
  32.         ans += w;
  33.     }
  34.     ans *= 2;
  35.     dfs(1, 0);
  36.     long long maximum = -INF;
  37.     for (int i = 1; i <= n; i++)
  38.     {
  39.         maximum = max(maximum, dis[i]);
  40.     }
  41.     ans -= maximum;
  42.     cout << ans;
  43. }
  44.  
  45. int main()
  46. {
  47.     int t = 1;
  48.     // cin>>t;
  49.     // go;
  50.     while (t--)
  51.     {
  52.         solve();
  53.         cout << "\n";
  54.     }
  55.     return 0;
  56. }
Success #stdin #stdout 0.01s 9712KB
comments (?)
stdin 
3
1 2 3
2 3 4
stdout 
7
https://ideone.com/XaqX3u
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!