Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct vertex // one point from the vector
- {
- vector <int> edges_connected;
- bool visited;
- int far_from_start;
- vertex()
- {
- visited = false;
- far_from_start = -1;
- edges_connected.erase(edges_connected.begin(), edges_connected.end());
- return;
- }
- };
- int main()
- {
- int vertices, edges, start_index, end_index;
- cin >> vertices >> edges;
- vector <vertex> buildings(vertices + 2); // the vector
- for (int i = 0; i < edges; i++) // entering edges
- {
- int a, b;
- cin >> a >> b;
- buildings[a].edges_connected.push_back(b);
- buildings[b].edges_connected.push_back(a);
- }
- cin >> start_index >> end_index;
- queue <int> bfs_queue; // the queue for BFS
- bfs_queue.push(start_index); // add the start point
- buildings[start_index].visited = true;
- buildings[start_index].far_from_start = 0;
- while (!bfs_queue.empty()) // BFS
- {
- int building = bfs_queue.front(); // the vertex index
- bfs_queue.pop();
- if (building == end_index) // found a way
- {
- cout << buildings[building].far_from_start; // return how far from start is the building
- return 0;
- }
- for (int i = 0; i < buildings[building].edges_connected.size(); i++) // check all connected vertices
- {
- if (!buildings[buildings[building].edges_connected[i]].visited) // if vertex is not checked
- {
- buildings[buildings[building].edges_connected[i]].visited = true; // check this vertex
- buildings[buildings[building].edges_connected[i]].far_from_start = buildings[building].far_from_start + 1;
- bfs_queue.push(buildings[building].edges_connected[i]); // add vertex to BFS queue
- }
- }
- }
- cout << 0; // cannot find a way
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement