Advertisement
Ginger_samurai

Untitled

Feb 3rd, 2020
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. int main()
  8. {
  9.     int n;
  10.     cin>>n;
  11.     vector<vector<int> >gm(n+1, vector<int>(n+1));
  12.     for(int i = 1; i <= n; i++)
  13.     {
  14.         for(int j = 1; j <= n; j++)
  15.         {
  16.             int x;
  17.             cin>>x;
  18.             gm[i][j] = x;
  19.         }
  20.     }
  21.     vector<vector<int> >g(n+1);
  22.     for(int i = 1; i <= n; i++)
  23.     {
  24.         for(int j = 1; j <= n; j++)
  25.         {
  26.             if(gm[i][j] == 1)
  27.             {
  28.                 g[i].push_back(j);
  29.             }
  30.         }
  31.     }
  32.     int s, k;
  33.     cin>>s>>k;
  34.     int undef = -1;
  35.     vector<int>dist(n+1, undef);
  36.     queue<int>q;
  37.     q.push(s);
  38.     dist[s] = 0;
  39.     while(!q.empty())
  40.     {
  41.         int x = q.front();
  42.         q.pop();
  43.         for(auto u: g[x])
  44.         {
  45.             if(dist[u] == undef)
  46.             {
  47.                 dist[u] = dist[x] + 1;
  48.                 q.push(u);
  49.             }
  50.         }
  51.     }
  52.     cout<<dist[k];
  53.  
  54.     return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement