Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.75 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. const int INF = 1e9;
  6.  
  7. void bfs(vector<vector<int>>& graph, vector<char>& add, vector<int>& dist, int st)
  8. {
  9.     int n = dist.size();
  10.     int vertex = st;
  11.     vector<int> vert;
  12.     vert.push_back(vertex);
  13.     bool ok = true;
  14.     while (ok)
  15.     {
  16.         vector<int> vert2;
  17.         for (int i = 0; i < vert.size(); i++)
  18.         {
  19.             for (int j = 0; j < graph[vert[i]].size(); j++)
  20.             {
  21.                 int v = graph[vert[i]][j];
  22.                 if (add[v] == false)
  23.                 {
  24.                     dist[v] = dist[vert[i]] + 1;
  25.                     add[v] = true;
  26.                     vert2.push_back(v);
  27.                 }
  28.             }
  29.         }
  30.         vert = vert2;
  31.         if (vert.size() == 0)
  32.         {
  33.             ok = false;
  34.         }
  35.     }
  36.    
  37. }
  38.  
  39. signed main()
  40. {
  41.     ios_base::sync_with_stdio(false);
  42.     cin.tie(NULL);
  43.  
  44.     int n;
  45.     cin >> n;
  46.     vector<vector<int>> graph0(n, vector<int>(n));
  47.     for (int i = 0; i < n; i++)
  48.     {
  49.         for (int j = 0; j < n; j++)
  50.         {
  51.             cin >> graph0[i][j];
  52.         }
  53.     }
  54.     vector<vector<int>> graph(n);
  55.     for (int i = 0; i < n; i++)
  56.     {
  57.         for (int j = 0; j < n; j++)
  58.         {
  59.             if (graph0[i][j] == 1)
  60.             {
  61.                 graph[i].push_back(j);
  62.             }
  63.         }
  64.     }
  65.     int st, en;
  66.     cin >> st >> en;
  67.     st--;
  68.     en--;
  69.     vector<char> add(n, false);
  70.     vector<int> dist(n, INF);
  71.     add[st] = true;
  72.     dist[st] = 0;
  73.     bfs(graph, add, dist, st);
  74.     if (dist[en] != INF)
  75.     {
  76.         cout << dist[en] << '\n';
  77.         if (dist[en] != 0)
  78.         {
  79.             int vertex = en;
  80.             vector<int> way;
  81.             way.push_back(vertex);
  82.             while (vertex != st)
  83.             {
  84.                 for (int i = 0; i < graph[vertex].size(); i++)
  85.                 {
  86.                     if (dist[graph[vertex][i]] == dist[vertex] - 1)
  87.                     {
  88.                         vertex = graph[vertex][i];
  89.                         way.push_back(vertex);
  90.                     }
  91.                 }
  92.             }
  93.             for (int i = way.size() - 1; i >= 0; i--)
  94.             {
  95.                 cout << way[i] + 1 << ' ';
  96.             }
  97.         }
  98.     }
  99.     else
  100.     {
  101.         cout << -1 << '\n';
  102.     }
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement