fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. struct Edge { int to; int w; };
  6.  
  7. int main() {
  8.     ios::sync_with_stdio(false);
  9.     cin.tie(nullptr);
  10.     int N, M;
  11.     if(!(cin >> N >> M)) return 0;
  12.  
  13.     vector<vector<Edge>> adj(N+1);
  14.     for (int i = 0; i < M; ++i) {
  15.         int u,v,w; cin >> u >> v >> w;
  16.         adj[u].push_back({v,w});
  17.         adj[v].push_back({u,w});
  18.     }
  19.     // 이웃 정점 번호 오름차순 정렬 (BFS 타이브레이크)
  20.     for (int u = 1; u <= N; ++u) {
  21.         sort(adj[u].begin(), adj[u].end(),
  22.              [](const Edge& a, const Edge& b){ return a.to < b.to; });
  23.     }
  24.  
  25.     // 1) BFS로 트리 구성, 방문 순서 기록
  26.     vector<int> order; order.reserve(N);
  27.     vector<int> parent(N+1, 0), depth(N+1, 0);
  28.     vector<ll> distw(N+1, 0);           // 루트(1)까지의 누적 가중치
  29.     vector<char> vis(N+1, 0);
  30.  
  31.     queue<int> q;
  32.     vis[1] = 1; parent[1] = 0; depth[1] = 0; distw[1] = 0;
  33.     q.push(1);
  34.  
  35.     while (!q.empty()) {
  36.         int u = q.front(); q.pop();
  37.         order.push_back(u);
  38.         for (auto [v, w] : adj[u]) {
  39.             if (!vis[v]) {
  40.                 vis[v] = 1;
  41.                 parent[v] = u;
  42.                 depth[v] = depth[u] + 1;
  43.                 distw[v] = distw[u] + w; // 트리 간선 가중치 누적
  44.                 q.push(v);
  45.             }
  46.         }
  47.     }
  48.  
  49.     // 2) LCA 준비 (binary lifting)
  50.     int LOG = 1;
  51.     while ((1<<LOG) <= N) ++LOG;
  52.     vector<vector<int>> up(LOG, vector<int>(N+1, 0));
  53.     up[0] = parent;
  54.     for (int k = 1; k < LOG; ++k) {
  55.         for (int v = 1; v <= N; ++v) {
  56.             int mid = up[k-1][v];
  57.             up[k][v] = (mid ? up[k-1][mid] : 0);
  58.         }
  59.     }
  60.  
  61.     auto lca = [&](int a, int b){
  62.         if (depth[a] < depth[b]) swap(a,b);
  63.         int diff = depth[a] - depth[b];
  64.         for (int k = 0; k < LOG; ++k)
  65.             if (diff & (1<<k)) a = up[k][a];
  66.         if (a == b) return a;
  67.         for (int k = LOG-1; k >= 0; --k) {
  68.             if (up[k][a] != up[k][b]) {
  69.                 a = up[k][a];
  70.                 b = up[k][b];
  71.             }
  72.         }
  73.         return parent[a];
  74.     };
  75.  
  76.     auto distT = [&](int a, int b)->ll{
  77.         int c = lca(a,b);
  78.         return distw[a] + distw[b] - 2LL*distw[c];
  79.     };
  80.  
  81.     // 3) 합 계산
  82.     ll ans = 0;
  83.     for (int i = 0; i+1 < (int)order.size(); ++i) {
  84.         ans += distT(order[i], order[i+1]);
  85.     }
  86.     ans += distT(order.back(), 1); // 마지막에서 1번으로 복귀
  87.  
  88.     cout << ans << '\n';
  89.     return 0;
  90. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
5 5
1 2 1
1 3 2
2 4 3
3 4 1
3 5 5
stdout
copy 
28
https://ideone.com/VAdz8c
language:
C++ (gcc 8.3)
created:
4 days 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!