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