Advertisement
Guest User

Untitled

a guest
Jul 17th, 2019
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.48 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef vector <int> v;
  6. typedef vector <v> vv;
  7.  
  8. void print(vv graph) {
  9.  
  10. int i = 0;
  11. for (auto x: graph) {
  12. cout << i << "-> ";
  13. i += 1;
  14. for (auto y: x) {
  15. cout << y << " ";
  16. }
  17. cout << endl;
  18. }
  19. }
  20.  
  21. void bfs (vv graph, v visited, int begin, int m) {
  22.  
  23. visited[begin] = 1;
  24. queue <int> queue1;
  25. queue1.push(begin);
  26. int distance[visited.size()] = {0};
  27.  
  28. while(!queue1.empty()) {
  29.  
  30. int front = queue1.front();
  31. queue1.pop();
  32.  
  33. for (auto x: graph[front]) {
  34.  
  35. if (!visited[x]) {
  36.  
  37. visited[x] = 1;
  38. distance[x] = distance[front] + 1;
  39. queue1.push(x);
  40. }
  41. }
  42. }
  43.  
  44. cout << distance[m] << endl;
  45. }
  46.  
  47. int main () {
  48. int n, m;
  49. cin >> n >> m;
  50.  
  51. if (m < n) {
  52. cout << n - m << endl;
  53. } else {
  54.  
  55. vv graph;
  56. v visited;
  57. int qnt_vertices = (m-1) * 2;
  58. graph.resize(qnt_vertices+1);
  59. visited.resize(qnt_vertices+1,0);
  60.  
  61. //graph[n-1].push_back((n-1)*2);
  62.  
  63. for (int i = 1; i <= qnt_vertices; i++) {
  64.  
  65. if (i > m - 1) {
  66. graph[i].push_back(i-1);
  67. } else {
  68. graph[i].push_back(i*2);
  69. graph[i].push_back(i-1);
  70. }
  71. }
  72. //print(graph);
  73. bfs(graph,visited,n,m);
  74. }
  75.  
  76. return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement