Advertisement
Guest User

Untitled

a guest
Jan 19th, 2019
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.08 KB | None | 0 0
  1. //#include "pch.h"
  2. #include <string>
  3. #include <iostream>
  4. #include <cmath>
  5. #include <vector>
  6. using namespace std;
  7. vector<int> G[101];
  8. bool visited[101];
  9. int dist[101];
  10. int parent[101];
  11.  
  12. int A[1000];
  13. int L = 0;
  14. int R = 0;
  15.  
  16. void push(int x) {
  17. A[R++] = x;
  18. }
  19.  
  20. int pop() {
  21. return A[L++];
  22. }
  23.  
  24. int size() {
  25. return R - L;
  26. }
  27.  
  28.  
  29. void bfs(int v) {
  30. push(v);
  31. visited[v] = true;
  32. dist[v] = 0;
  33.  
  34. while (size() > 0) {
  35. int x = pop();
  36. for (int i = 0; i < G[x].size(); ++i) {
  37. if (!visited[G[x][i]]) {
  38. push(G[x][i]);
  39. visited[G[x][i]] = true;
  40. dist[G[x][i]] = dist[x] + 1;
  41. parent[G[x][i]] = x;
  42. }
  43. }
  44. }
  45. }
  46.  
  47. int main() {
  48. int n, a, b;
  49.  
  50. for (int i = 0; i < 101; i++) {
  51. dist[i] = -1;
  52. }
  53.  
  54. cin >> n;
  55.  
  56. for (int i = 0; i < n; i++)
  57. for (int j = 0; j < n; j++) {
  58. cin >> a;
  59. if (a) {
  60. G[i].push_back(j);
  61. }
  62. }
  63.  
  64. cin >> a >> b;
  65. bfs(--b);
  66. cout << dist[--a] << endl;
  67. int t = a;
  68. if (dist[a] > 0) {
  69. cout << t + 1 << " ";
  70. do {
  71. t = parent[t];
  72. cout << t + 1 << " ";
  73.  
  74. } while (t != b);
  75. }
  76.  
  77. return 0;
  78.  
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement