Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#include "pch.h"
- #include <string>
- #include <iostream>
- #include <cmath>
- #include <vector>
- using namespace std;
- vector<int> G[101];
- bool visited[101];
- int dist[101];
- int parent[101];
- int A[1000];
- int L = 0;
- int R = 0;
- void push(int x) {
- A[R++] = x;
- }
- int pop() {
- return A[L++];
- }
- int size() {
- return R - L;
- }
- void bfs(int v) {
- push(v);
- visited[v] = true;
- dist[v] = 0;
- while (size() > 0) {
- int x = pop();
- for (int i = 0; i < G[x].size(); ++i) {
- if (!visited[G[x][i]]) {
- push(G[x][i]);
- visited[G[x][i]] = true;
- dist[G[x][i]] = dist[x] + 1;
- parent[G[x][i]] = x;
- }
- }
- }
- }
- int main() {
- int n, a, b;
- for (int i = 0; i < 101; i++) {
- dist[i] = -1;
- }
- cin >> n;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++) {
- cin >> a;
- if (a) {
- G[i].push_back(j);
- }
- }
- cin >> a >> b;
- bfs(--b);
- cout << dist[--a] << endl;
- int t = a;
- if (dist[a] > 0) {
- cout << t + 1 << " ";
- do {
- t = parent[t];
- cout << t + 1 << " ";
- } while (t != b);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement