Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef vector <int> v;
- typedef vector <v> vv;
- void print(vv graph) {
- int i = 0;
- for (auto x: graph) {
- cout << i << "-> ";
- i += 1;
- for (auto y: x) {
- cout << y << " ";
- }
- cout << endl;
- }
- }
- void bfs (vv graph, v visited, int begin, int m) {
- visited[begin] = 1;
- queue <int> queue1;
- queue1.push(begin);
- int distance[visited.size()] = {0};
- while(!queue1.empty()) {
- int front = queue1.front();
- queue1.pop();
- for (auto x: graph[front]) {
- if (!visited[x]) {
- visited[x] = 1;
- distance[x] = distance[front] + 1;
- queue1.push(x);
- }
- }
- }
- cout << distance[m] << endl;
- }
- int main () {
- int n, m;
- cin >> n >> m;
- if (m < n) {
- cout << n - m << endl;
- } else {
- vv graph;
- v visited;
- int qnt_vertices = (m-1) * 2;
- graph.resize(qnt_vertices+1);
- visited.resize(qnt_vertices+1,0);
- //graph[n-1].push_back((n-1)*2);
- for (int i = 1; i <= qnt_vertices; i++) {
- if (i > m - 1) {
- graph[i].push_back(i-1);
- } else {
- graph[i].push_back(i*2);
- graph[i].push_back(i-1);
- }
- }
- //print(graph);
- bfs(graph,visited,n,m);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement