Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <string>
- #include <sstream>
- #include <algorithm>
- #include <vector>
- #include <stdlib.h>
- #include <stdio.h>
- #include <fstream>
- #include <stack>
- #include <map>
- #include <cstring>
- #include <cmath>
- #include <set>
- #include <iterator>
- #include <cmath>
- #include <locale>
- #include <queue>
- #include <deque>
- #include <stack>
- using namespace std;
- const int MOD = 1000000000;
- void VIVOD(vector<vector<int> > vec2, int n, int m)
- {
- for (auto i = 0; i < n; ++i)
- {
- for (auto j = 0; j < m; ++j)
- {
- cout << vec2[i][j] << " ";
- }
- cout << endl;
- }
- }
- void VIVOD1(vector<int> vec)
- {
- for (auto el : vec)
- {
- cout << el << " ";
- }
- }
- void VIVODq(queue<int> que)
- {
- queue<int> q2 = que;
- while (!q2.empty())
- {
- int a = q2.front();
- q2.pop();
- cout << a << " ";
- }
- cout << endl;
- }
- int main()
- {
- /*
- int n, a, m;
- cin >> n;
- vector<int> vec;
- for (auto i = 0; i < n; i++) {
- cin >> a;
- vec.push_back(a);
- }
- cin >> m;
- vector<int> vec2(m + 1, MOD), vec3(m + 1);
- vec2[0] = 0;
- for (auto j = 1; j < m + 1; j++) {
- for (auto i = 0; i < n; i++)
- if (j - vec[i] >= 0 && vec2[j - vec[i]] < vec2[j]) {
- vec2[j] = vec2[j - vec[i]];
- vec3[j] = vec[i];
- }
- vec2[j]++;
- }
- if (vec2[m] >= MOD)
- cout << "No solution";
- else
- while (m > 0) {
- cout << vec3[m] << ' ';
- m -= vec3[m];
- }
- */
- int N, p, w, b;
- queue<int> que;
- cin >> N;
- vector<vector<int > > vec2(N, vector<int>(N));
- vector<int> vec(N), answ;
- for (auto i = 0; i < N; ++i)
- {
- vec[i] = MOD;
- for (auto j = 0; j < N; ++j)
- cin >> vec2[i][j];
- }
- cin >> w >> p;
- vec[w - 1] = 0;
- que.push(w - 1);
- // VIVOD1(vec, N);
- while (!que.empty()) {
- // cout << endl;
- // VIVODq(que);
- answ.push_back(que.front() + 1);
- // cout << endl;
- b = que.front();
- que.pop();
- for (auto j = 0; j < N; ++j)
- if (vec2[b][j] && vec[j] > vec[b] + 1) {
- vec[j] = vec[b] + 1;
- que.push(j);
- }
- }
- // VIVOD1(vec, N);
- // VIVOD(vec2, N, N);
- if (vec[p - 1] < MOD) {
- cout << vec[p - 1] << endl;
- if (vec[p - 1] != 0)
- VIVOD1(answ);
- }
- else
- cout << -1;
- return 0;
- }
- /*
- 5
- 0 1 0 0 1
- 1 0 1 0 0
- 0 1 0 0 0
- 0 0 0 0 0
- 1 0 0 0 0
- 3 5
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement