Advertisement
OMEGAHEAD_MonkoX

Untitled

Mar 30th, 2020
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <string>
  4. #include <sstream>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <stdlib.h>
  8. #include <stdio.h>
  9. #include <fstream>
  10. #include <stack>
  11. #include <map>
  12. #include <cstring>
  13. #include <cmath>
  14. #include <set>
  15. #include <iterator>
  16. #include <cmath>
  17. #include <locale>
  18. #include <queue>
  19. #include <deque>
  20. #include <stack>
  21.  
  22.  
  23. using namespace std;
  24.  
  25.  
  26.  
  27. const int MOD = 1000000000;
  28.  
  29. void VIVOD(vector<vector<int> > vec2, int n, int m)
  30. {
  31. for (auto i = 0; i < n; ++i)
  32. {
  33. for (auto j = 0; j < m; ++j)
  34. {
  35. cout << vec2[i][j] << " ";
  36. }
  37. cout << endl;
  38. }
  39. }
  40.  
  41. void VIVOD1(vector<int> vec)
  42. {
  43. for (auto el : vec)
  44. {
  45. cout << el << " ";
  46. }
  47. }
  48. void VIVODq(queue<int> que)
  49. {
  50. queue<int> q2 = que;
  51. while (!q2.empty())
  52. {
  53. int a = q2.front();
  54. q2.pop();
  55. cout << a << " ";
  56. }
  57. cout << endl;
  58. }
  59.  
  60.  
  61. int main()
  62. {
  63. /*
  64. int n, a, m;
  65. cin >> n;
  66. vector<int> vec;
  67.  
  68. for (auto i = 0; i < n; i++) {
  69. cin >> a;
  70. vec.push_back(a);
  71. }
  72.  
  73. cin >> m;
  74. vector<int> vec2(m + 1, MOD), vec3(m + 1);
  75. vec2[0] = 0;
  76.  
  77. for (auto j = 1; j < m + 1; j++) {
  78.  
  79. for (auto i = 0; i < n; i++)
  80.  
  81. if (j - vec[i] >= 0 && vec2[j - vec[i]] < vec2[j]) {
  82. vec2[j] = vec2[j - vec[i]];
  83. vec3[j] = vec[i];
  84. }
  85.  
  86. vec2[j]++;
  87. }
  88.  
  89. if (vec2[m] >= MOD)
  90. cout << "No solution";
  91. else
  92. while (m > 0) {
  93. cout << vec3[m] << ' ';
  94. m -= vec3[m];
  95. }
  96. */
  97. int N, p, w, b;
  98. queue<int> que;
  99. cin >> N;
  100. vector<vector<int > > vec2(N, vector<int>(N));
  101. vector<int> vec(N), answ;
  102. for (auto i = 0; i < N; ++i)
  103. {
  104. vec[i] = MOD;
  105. for (auto j = 0; j < N; ++j)
  106. cin >> vec2[i][j];
  107. }
  108. cin >> w >> p;
  109. vec[w - 1] = 0;
  110. que.push(w - 1);
  111. // VIVOD1(vec, N);
  112. while (!que.empty()) {
  113. // cout << endl;
  114. // VIVODq(que);
  115. answ.push_back(que.front() + 1);
  116. // cout << endl;
  117. b = que.front();
  118. que.pop();
  119. for (auto j = 0; j < N; ++j)
  120. if (vec2[b][j] && vec[j] > vec[b] + 1) {
  121. vec[j] = vec[b] + 1;
  122. que.push(j);
  123. }
  124. }
  125. // VIVOD1(vec, N);
  126. // VIVOD(vec2, N, N);
  127. if (vec[p - 1] < MOD) {
  128. cout << vec[p - 1] << endl;
  129. if (vec[p - 1] != 0)
  130. VIVOD1(answ);
  131. }
  132. else
  133. cout << -1;
  134.  
  135. return 0;
  136. }
  137.  
  138. /*
  139. 5
  140. 0 1 0 0 1
  141. 1 0 1 0 0
  142. 0 1 0 0 0
  143. 0 0 0 0 0
  144. 1 0 0 0 0
  145. 3 5
  146.  
  147.  
  148.  
  149.  
  150.  
  151. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement