Advertisement
georgiy110802

BFS

May 2nd, 2022
1,067
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.76 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = (int)1e9;
  6.  
  7. main()
  8. {
  9.     int n, m, ans = 0;
  10.     cin >> n;
  11.     vector<vector<int>> g(n + 1, vector<int> (n + 1));
  12.     for(int i = 1; i <= n; i++)
  13.         for(int j = 1; j <= n; j++)
  14.             cin >> g[i][j];
  15.     int start, finish;
  16.     cin >> start >> finish;
  17.     vector<int> p(n + 1, INF);
  18.     p[start] = 0;
  19.     queue<int> q;
  20.     q.push(start);
  21.     while(!q.empty())
  22.     {
  23.         int cur = q.front();
  24.         q.pop();
  25.         for(int i = 1; i <= n; i++)
  26.             if(g[cur][i] && p[i] == INF)
  27.             {
  28.                 p[i] = p[cur] + 1;
  29.                 q.push(i);
  30.             }
  31.     }
  32.     if(p[finish] == INF)
  33.         cout << -1;
  34.     else
  35.         cout << p[finish];
  36. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement