Advertisement
Guest User

ha-ha

a guest
Jul 20th, 2014
377
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.15 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <queue>
  6. #include <queue>
  7. #include <math.h>
  8. using namespace std;
  9. int arr[107][107],d[107],p[107];
  10. bool used[107];
  11. int main()
  12. {
  13. int i,j,n,s,m;
  14. cin>>n;
  15. for (i=1; i<=n; ++i)
  16. {
  17. for (j=1; j<=n; ++j)
  18. {
  19. cin>>arr[i][j];
  20. }
  21. }
  22. cin>>s>>m;
  23. queue<int> q;
  24. q.push(s);
  25. vector<bool> used(n);
  26. used[s]=true;
  27. p[s]=-1;
  28. while (!q.empty())
  29. {
  30. int v=q.front();
  31. q.pop();
  32. for (i=1; i<=n; ++i)
  33. {
  34. int to = arr[v][i];
  35. if (to==1)
  36. {
  37. if (!used[i])
  38. {
  39. used[i]=true;
  40. q.push(i);
  41. d[i]=d[v]+1;
  42. p[i]=v;
  43. }
  44. }
  45. }
  46.  
  47. }
  48. if (!used[m])
  49. {
  50. cout<<-1;
  51. }
  52. else
  53. {
  54. cout<<d[m]<<'\n';
  55. vector<int> path;
  56. for (int v=m; v!=-1; v=p[v])
  57. path.push_back(v);
  58. for (i=path.size()-1; i>=0; --i) cout<<path[i]<<" ";
  59. }
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement