Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n, a, b, pr[5000], dist[5000], p[5000], ans;
- vector <int> x[5000];
- queue <int> q;
- int main(){
- cin >> n;
- for(int i = 1; i <= n; i++){
- for(int j = 1; j <= n; j++){
- cin >> a;
- if(a){
- x[i].push_back(j);
- x[j].push_back(i);
- }
- }
- }
- cin >> a >> b;
- q.push(a);
- pr[a] = 1;
- dist[a] = 0;
- p[a] = -1;
- while(!q.empty()){
- int v = q.front();
- q.pop();
- for(int i = 0; i < x[v].size(); i++){
- int to = x[v][i];
- if(!pr[to]){
- pr[to] = 1;
- q.push(to);
- dist[to] = dist[v] + 1;
- p[to] = v;
- }
- }
- }
- if(!pr[b]){
- cout << -1;
- }
- else{
- vector <int> path;
- for(int i = b; i != -1; i = p[i]){
- path.push_back(i);
- ans++;
- }
- reverse(path.begin(), path.end());
- if(ans - 1){
- cout << ans - 1 << endl;
- for(int i = 0; i < path.size(); i++){
- cout << path[i] << " ";
- }
- }
- else{
- cout << ans - 1;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement