GastonFontenla

HackerRank: Breadth First Search: Shortest Reach

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