Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- const int INF = 1e9;
- void bfs(vector<vector<int>>& graph, vector<char>& add, vector<int>& dist, int st)
- {
- int n = dist.size();
- int vertex = st;
- vector<int> vert;
- vert.push_back(vertex);
- bool ok = true;
- while (ok)
- {
- vector<int> vert2;
- for (int i = 0; i < vert.size(); i++)
- {
- for (int j = 0; j < graph[vert[i]].size(); j++)
- {
- int v = graph[vert[i]][j];
- if (add[v] == false)
- {
- dist[v] = dist[vert[i]] + 1;
- add[v] = true;
- vert2.push_back(v);
- }
- }
- }
- vert = vert2;
- if (vert.size() == 0)
- {
- ok = false;
- }
- }
- }
- signed main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int n;
- cin >> n;
- vector<vector<int>> graph0(n, vector<int>(n));
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < n; j++)
- {
- cin >> graph0[i][j];
- }
- }
- vector<vector<int>> graph(n);
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < n; j++)
- {
- if (graph0[i][j] == 1)
- {
- graph[i].push_back(j);
- }
- }
- }
- int st, en;
- cin >> st >> en;
- st--;
- en--;
- vector<char> add(n, false);
- vector<int> dist(n, INF);
- add[st] = true;
- dist[st] = 0;
- bfs(graph, add, dist, st);
- if (dist[en] != INF)
- {
- cout << dist[en] << '\n';
- if (dist[en] != 0)
- {
- int vertex = en;
- vector<int> way;
- way.push_back(vertex);
- while (vertex != st)
- {
- for (int i = 0; i < graph[vertex].size(); i++)
- {
- if (dist[graph[vertex][i]] == dist[vertex] - 1)
- {
- vertex = graph[vertex][i];
- way.push_back(vertex);
- }
- }
- }
- for (int i = way.size() - 1; i >= 0; i--)
- {
- cout << way[i] + 1 << ' ';
- }
- }
- }
- else
- {
- cout << -1 << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement