GastonFontenla

HackerRank: Prim's (MST): Special Subtree

Jun 5th, 2016
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. #define ii pair<int, int>
  6. #define iii pair<ii, int>
  7.  
  8. using namespace std;
  9.  
  10. struct Grafo
  11. {
  12.     vector <vector <ii> > adj;
  13.  
  14.     void leer()
  15.     {
  16.         int nodos, aristas, f, t, w, s;
  17.         cin >> nodos >> aristas;
  18.  
  19.         adj = vector <vector <ii> > (nodos+1, vector <ii>());
  20.  
  21.         for(int i=0; i<aristas; i++)
  22.         {
  23.             cin >> f >> t >> w;
  24.             adj[f].push_back(ii(w, t));
  25.             adj[t].push_back(ii(w, f));
  26.         }
  27.  
  28.         cin >> s;
  29.  
  30.         vector <bool> v(nodos+1, false);
  31.         priority_queue <iii, vector <iii>, greater<iii> > pq;
  32.         vector <iii> res;
  33.  
  34.         for(int i=0; i<adj[s].size(); i++)
  35.             pq.push(make_pair(adj[s][i], s));
  36.  
  37.         v[s] = 1;
  38.         int usados = 0;
  39.  
  40.         while(usados < nodos-1)
  41.         {
  42.             iii p = pq.top();
  43.             pq.pop();
  44.  
  45.             int n = p.first.second;
  46.             if(!v[n])
  47.             {
  48.                 usados++;
  49.                 v[n] = true;
  50.                 res.push_back(p);
  51.  
  52.                 for(int i=0; i<adj[n].size(); i++)
  53.                     if(!v[adj[n][i].second])
  54.                         pq.push(make_pair(adj[n][i], n));
  55.             }
  56.         }
  57.  
  58.         int mst = 0;
  59.         for(int i=0; i<res.size(); i++)
  60.             mst += res[i].first.first;
  61.         cout << mst << endl;
  62.     }
  63. };
  64.  
  65. int main()
  66. {
  67.     Grafo g;
  68.     g.leer();
  69.     return 0;
  70. }
Add Comment
Please, Sign In to add comment