fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //toast418
  5. #define ffor(i,o,f)		   for(int i = o; i < f; i++)
  6. #define pb 				   push_back
  7. #define mp                 make_pair
  8. #define all(a)             (a).begin(), (a).end()
  9. #define F                  first
  10. #define S                  second
  11. #define PI 				   3.14159265358979323846264338327950
  12. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  13. #define endl 			   '\n'
  14. #define sz(x)              ((int)(x).size())
  15. typedef long long          ll;
  16. typedef pair < int, int >  pii;
  17. typedef vector < int >     vi;
  18. typedef vector < pii >     vii;
  19. typedef vector < vi > 	   gi;
  20. typedef vector < ll >      vll;
  21. typedef map < int, int >   mii;
  22.  
  23. int t, n, m, u, v, groups;
  24. const int tam = 1005;
  25. gi g;
  26. vi dist;
  27. vi parent;
  28. queue < int > q;
  29.  
  30. void bfs(int nd){
  31.     dist[nd] = 0;
  32.     parent[nd] = -1;
  33.     q.push(nd);
  34.     while(!q.empty()){
  35.         nd = q.front();
  36.         q.pop();
  37.         ffor(i, 0, sz(g[nd])){
  38.             int nxt = g[nd][i];
  39.             if(dist[nxt] == -1){
  40.                 dist[nxt] = dist[nd] + 1;
  41.                 parent[nxt] = nd;
  42.                 q.push(nxt);
  43.             }
  44.         }
  45.     }
  46. }
  47.  
  48. void printPath(int nd){
  49.     vi path;
  50.     while(nd != -1){
  51.         path.pb(nd);
  52.         nd = parent[nd];
  53.     }
  54.     reverse(all(path));
  55.     ffor(i, 0, sz(path)){
  56.         if(i > 0){
  57.             cout << " -> ";
  58.         }
  59.         cout << path[i];
  60.     }
  61. }
  62.  
  63. int main()
  64. {
  65.     g.assign(tam, vi ());
  66.     dist.assign(tam, -1);
  67.     parent.assign(tam, -1);
  68.  
  69.     g[0].pb(2);
  70.     g[2].pb(0);
  71.     g[0].pb(3);
  72.     g[3].pb(0);
  73.     g[1].pb(3);
  74.     g[3].pb(1);
  75.     g[1].pb(6);
  76.     g[6].pb(1);
  77.     g[2].pb(3);
  78.     g[3].pb(2);
  79.     g[2].pb(4);
  80.     g[4].pb(2);
  81.     g[2].pb(5);
  82.     g[5].pb(2);
  83.     g[4].pb(5);
  84.     g[5].pb(4);
  85.     g[3].pb(7);
  86.     g[7].pb(3);
  87.     g[6].pb(7);
  88.     g[7].pb(6);
  89.  
  90.     bfs(0);
  91.  
  92.     ffor(i, 0, 8){
  93.         cout << "Nodo " << i << ": ";
  94.         if(dist[i] == -1){
  95.             cout << "inalcanzable" << endl;
  96.             continue;
  97.         }
  98.         cout << "distancia = " << dist[i] << ", ruta = ";
  99.         printPath(i);
  100.         cout << endl;
  101.     }
  102. }
  103.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Nodo 0: distancia = 0, ruta = 0
Nodo 1: distancia = 2, ruta = 0 -> 3 -> 1
Nodo 2: distancia = 1, ruta = 0 -> 2
Nodo 3: distancia = 1, ruta = 0 -> 3
Nodo 4: distancia = 2, ruta = 0 -> 2 -> 4
Nodo 5: distancia = 2, ruta = 0 -> 2 -> 5
Nodo 6: distancia = 3, ruta = 0 -> 3 -> 1 -> 6
Nodo 7: distancia = 2, ruta = 0 -> 3 -> 7
https://ideone.com/w3RZlv
language:
C++14 (gcc 8.3)
created:
2 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!