Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <queue>
- #include <queue>
- #include <math.h>
- using namespace std;
- int arr[107][107],d[107],p[107];
- bool used[107];
- int main()
- {
- int i,j,n,s,m;
- cin>>n;
- for (i=1; i<=n; ++i)
- {
- for (j=1; j<=n; ++j)
- {
- cin>>arr[i][j];
- }
- }
- cin>>s>>m;
- queue<int> q;
- q.push(s);
- vector<bool> used(n);
- used[s]=true;
- p[s]=-1;
- while (!q.empty())
- {
- int v=q.front();
- q.pop();
- for (i=1; i<=n; ++i)
- {
- int to = arr[v][i];
- if (to==1)
- {
- if (!used[i])
- {
- used[i]=true;
- q.push(i);
- d[i]=d[v]+1;
- p[i]=v;
- }
- }
- }
- }
- if (!used[m])
- {
- cout<<-1;
- }
- else
- {
- cout<<d[m]<<'\n';
- vector<int> path;
- for (int v=m; v!=-1; v=p[v])
- path.push_back(v);
- for (i=path.size()-1; i>=0; --i) cout<<path[i]<<" ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement