Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<algorithm>
- #include<cmath>
- #include<map>
- #include<queue>
- #include<string>
- #include<set>
- using namespace std;
- typedef long long ll;
- int main()
- {
- ll n;
- cin >> n;
- vector<vector<ll>>g(n, vector<ll>(n,1e18));
- ll m;
- cin >> m;
- vector<vector<ll>>ed(m);
- map<ll, vector<ll>>a;
- for (int i = 0; i < m; i++) {
- ll k;
- cin >> k;
- for (int j = 0; j < k; j++) {
- ll x;
- cin >> x;
- ed[i].push_back(x);
- a[x].push_back(i);
- }
- }
- ll s, f;
- cin >> s >> f;
- vector<ll>d(n+1,1e18);
- queue<ll>q;
- q.push(s);
- d[s] = -1;
- while (!q.empty()) {
- ll v = q.front();
- q.pop();
- for (auto i : a[v]) {
- for (auto j : ed[i])
- if (d[j] > d[v] + 1) {
- d[j] = min(d[j], d[v] + 1);
- q.push(j);
- }
- }
- }
- if (d[f] == 1e18)
- cout << -1;
- else if (f == s)
- cout << 0;
- else
- cout << d[f];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement