Advertisement
eynizadeMurad

Breadth - First - Search

Mar 28th, 2017
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.64 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. queue<int>q;
  4. int adj[101][101],d[101],p[101],n,c[101],a,b;
  5. void bfs(int s) {
  6.     for (int i=1;i<=n;i++) {
  7.         d[i]=1000000000;
  8.     }
  9.     d[s] = 0;
  10.     q.push(s);
  11.     c[s]=1;
  12.     while (!q.empty()) {
  13.        int u = q.front();
  14.        q.pop();
  15.        for (int i=1;i<=n;i++) {
  16.         if (adj[u][i]==1 && c[i]==0) {
  17.             d[i] = d[u] + 1;
  18.             c[i]=1;
  19.             q.push(i);
  20.             p[i]=u;
  21.            }
  22.        }
  23.        c[u]==2;
  24.     }
  25. }
  26. int main() {
  27.     cin>>n>>a>>b;  
  28.     int ones=0;
  29.     for (int i=1;i<=n;i++)
  30.     for (int j=1;j<=n;j++)
  31.     cin>>adj[i][j];
  32. bfs(a);
  33. if (d[b]==1000000000)
  34. cout<<0<<endl;
  35. else
  36. cout<<d[b]<<endl;
  37.    
  38.     return 0;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement