Advertisement
hurmawe

Путь в графе_0

Dec 19th, 2020
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.93 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. void BFS(const vector<vector<int>>& array,const int& start,int& end, vector<int>& output)
  8. {
  9.     queue<int> Q;
  10.  
  11.     vector<int> distance(array.size(), -1);
  12.     vector<int> parent(array.size(),-2);
  13.     parent[start-1] = -1;
  14.     distance[start-1] = 0;
  15.     Q.push(start-1);
  16.     int vr;
  17.     while(Q.size()) {
  18.         vr=Q.front();
  19.         Q.pop();
  20.         for (int i = 0; i < array.size(); i++)
  21.         {
  22.             if (array[vr][i] == 1)
  23.             {
  24.                 if (distance[i] == -1)
  25.                 {
  26.                     Q.push(i);
  27.                     parent[i]=vr;
  28.                     distance[i] = distance[vr] + 1;
  29.                 }
  30.                 if(i == end-1)
  31.                 {
  32.                     if(distance[i] == 0)
  33.                     {
  34.                         cout << distance[i];
  35.                         exit(0);
  36.                     }
  37.                         cout << distance[i] << endl;
  38.                         int j = end-1;
  39.                         while(j != -1)
  40.                         {
  41.                             output.push_back(j);
  42.                             j=parent[j];
  43.                         }
  44.                         end = 0;
  45.                         return;
  46.                 }
  47.             }
  48.         }
  49.  
  50.     }
  51. }
  52.  
  53. int main(){
  54.     int32_t         lenght;
  55.     int32_t         start;
  56.     int32_t         end;
  57.  
  58.  
  59.     cin >> lenght;
  60.  
  61.     vector<vector<int>>  array(lenght);
  62.     for(int i =0; i < lenght; i++) {
  63.         array[i].resize(lenght);
  64.         for (int j = 0; j < lenght; ++j) {
  65.             cin >> array[i][j];
  66.         }
  67.     }
  68.     cin >> start >> end;
  69.     vector<int> output;
  70.  
  71.     BFS(array,start,end,output);
  72.     if(end == 0)
  73.     {
  74.         for (int i = output.size(); i > 0; i--) {
  75.             cout << output[i - 1]+1 << " ";
  76.         }
  77.     }
  78.     else
  79.     {
  80.         cout << -1;
  81.     }
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement