Advertisement
PlanttPastes

ИИ - Алгоритми 2021 задачи за решавање: Суперхерој

Oct 19th, 2021
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct vertex // one point from the vector
  4. {
  5.     vector <int> edges_connected;
  6.     bool visited;
  7.     int far_from_start;
  8.     vertex()
  9.     {
  10.         visited = false;
  11.         far_from_start = -1;
  12.         edges_connected.erase(edges_connected.begin(), edges_connected.end());
  13.         return;
  14.     }
  15. };
  16. int main()
  17. {
  18.     int vertices, edges, start_index, end_index;
  19.     cin >> vertices >> edges;
  20.     vector <vertex> buildings(vertices + 2); // the vector
  21.     for (int i = 0; i < edges; i++) // entering edges
  22.     {
  23.         int a, b;
  24.         cin >> a >> b;
  25.         buildings[a].edges_connected.push_back(b);
  26.         buildings[b].edges_connected.push_back(a);
  27.     }
  28.     cin >> start_index >> end_index;
  29.     queue <int> bfs_queue; // the queue for BFS
  30.     bfs_queue.push(start_index); // add the start point
  31.     buildings[start_index].visited = true;
  32.     buildings[start_index].far_from_start = 0;
  33.     while (!bfs_queue.empty()) // BFS
  34.     {
  35.         int building = bfs_queue.front(); // the vertex index
  36.         bfs_queue.pop();
  37.         if (building == end_index) // found a way
  38.         {
  39.             cout << buildings[building].far_from_start; // return how far from start is the building
  40.             return 0;
  41.         }
  42.         for (int i = 0; i < buildings[building].edges_connected.size(); i++) // check all connected vertices
  43.         {
  44.             if (!buildings[buildings[building].edges_connected[i]].visited) // if vertex is not checked
  45.             {
  46.                 buildings[buildings[building].edges_connected[i]].visited = true; // check this vertex
  47.                 buildings[buildings[building].edges_connected[i]].far_from_start = buildings[building].far_from_start + 1;
  48.                 bfs_queue.push(buildings[building].edges_connected[i]); // add vertex to BFS queue
  49.             }
  50.         }
  51.     }
  52.     cout << 0; // cannot find a way
  53.     return 0;
  54. }
  55.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement