Advertisement
konchin_shih

a129

Feb 5th, 2021
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.04 KB | None | 0 0
  1. #include".\template\headers.hpp"
  2.  
  3. //#define MULTI_TASKCASE
  4. using namespace abb;
  5. using namespace output;
  6. using namespace rit;
  7. using namespace wit;
  8.  
  9. inline void init() {
  10.  
  11. }
  12.  
  13. struct edge {
  14.     int a, b; ll v;
  15. };
  16. bool operator<(edge a, edge b) {
  17.     return a.v < b.v;
  18. };
  19.  
  20. inline void solve() {
  21.     int n, m;
  22.     while (cin >> n >> m) {
  23.         V<edge> v(m);
  24.         for (auto& i : v)
  25.             cin >> i.a >> i.b >> i.v;
  26.         sort(v.begin(), v.end());
  27.         V<int> d(n);
  28.         iota(d.begin(), d.end(), 0);
  29.         F<int(int)> find = [&](int x) {
  30.             return x == d[x] ? x : (d[x] = find(d[x]));
  31.         };
  32.         auto merge = [&](int a, int b) {
  33.             d[find(a)] = find(b);
  34.         };
  35.         ll ans = 0;
  36.         for (auto& i : v)
  37.             if (find(i.a) != find(i.b))
  38.                 ans += i.v, merge(i.a, i.b);
  39.         for (int i = 1; i < n; i++)
  40.             if (find(0) != find(i))
  41.                 goto no_result;
  42.         cout << ans << endl;
  43.         continue;
  44. no_result :
  45.         cout << -1 << endl;
  46.     }
  47. }
  48.  
  49. main() {
  50.     ios::sync_with_stdio(false);
  51.     init();
  52.     int t = 1;
  53. #ifdef MULTI_TASKCASE
  54.     cin >> t; cin.ignore();
  55. #endif
  56.     while (t--) solve();
  57.     return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement