SHARE
TWEET

Untitled

a guest Jan 22nd, 2020 105 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define INF 10e9
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <stdio.h>
  6. #include <queue>
  7. #include <stack>
  8. #include <climits>
  9.  
  10. using namespace std;
  11.  
  12. long n, m, root = 0, dest, len = 0;
  13.  
  14. vector <vector<long>> gr;
  15. vector <vector<long>> rebro;
  16. vector <long> derevo;
  17. vector <bool> used;
  18. vector <int> parent;
  19. queue <long> minpath;
  20.  
  21. int main()
  22. {
  23.     //freopen("input.txt", "r", stdin);
  24.     //freopen("output.txt", "w", stdout);
  25.     scanf("%ld%ld", &n, &m);
  26.     gr.resize(n);
  27.     rebro.resize(m);
  28.     derevo.resize(m + 1);
  29.  
  30.     for (long i = 0; i < n; i++)
  31.     {
  32.         gr[i].resize(n);
  33.         derevo[i] = i;
  34.     }
  35.    
  36.     for (long i = 0; i < m; i++)
  37.     {
  38.         rebro[i].resize(3);
  39.         scanf("%ld%ld%ld", &rebro[i][1], &rebro[i][2], &rebro[i][0]);
  40.     }
  41.     sort(rebro.begin(), rebro.end());
  42.  
  43.     for (long i = 0; i < m; i++)
  44.     {
  45.         long a = rebro[i][1];
  46.         long b = rebro[i][2];
  47.         long c = rebro[i][0];
  48.         if (derevo[a] != derevo[b])
  49.         {
  50.             len += c;
  51.             gr[a - 1][b - 1] = c;
  52.             gr[b - 1][a - 1] = c;
  53.             long aa = derevo[a];
  54.             long bb = derevo[b];
  55.             for (long j = 0; j < m + 1; j++)
  56.             {
  57.                 if (derevo[j] == bb)
  58.                 {
  59.                     derevo[j] = aa;
  60.                 }
  61.             }
  62.         }
  63.     }
  64.  
  65.     printf("%ld\n", len);
  66.  
  67.     for (long i = 0; i < n; i++)
  68.     {
  69.         for (long j = 0; j < n; j++)
  70.         {
  71.             printf("%ld ", gr[i][j]);
  72.         }
  73.         printf("\n");
  74.     }
  75.     system("PAUSE");
  76.     return 0;
  77. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top