Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2018
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.11 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cmath>
  5. #include<map>
  6. #include<queue>
  7. #include<string>
  8. #include<set>
  9. using namespace std;
  10. typedef long long ll;
  11. int main()
  12. {
  13. ll n;
  14. cin >> n;
  15. vector<vector<ll>>g(n, vector<ll>(n,1e18));
  16. ll m;
  17. cin >> m;
  18. vector<vector<ll>>ed(m);
  19. map<ll, vector<ll>>a;
  20. for (int i = 0; i < m; i++) {
  21. ll k;
  22. cin >> k;
  23. for (int j = 0; j < k; j++) {
  24. ll x;
  25. cin >> x;
  26. ed[i].push_back(x);
  27. a[x].push_back(i);
  28. }
  29. }
  30. ll s, f;
  31. cin >> s >> f;
  32. vector<ll>d(n+1,1e18);
  33. queue<ll>q;
  34. q.push(s);
  35. d[s] = -1;
  36. while (!q.empty()) {
  37. ll v = q.front();
  38. q.pop();
  39. for (auto i : a[v]) {
  40. for (auto j : ed[i])
  41. if (d[j] > d[v] + 1) {
  42. d[j] = min(d[j], d[v] + 1);
  43. q.push(j);
  44. }
  45. }
  46. }
  47. if (d[f] == 1e18)
  48. cout << -1;
  49. else if (f == s)
  50. cout << 0;
  51. else
  52. cout << d[f];
  53. return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement