Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2018
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
CSS 1.43 KB | None | 0 0
  1. #include <algorithm>
  2. #include <cstdint>
  3. #include <iostream>
  4. #include <queue>
  5. #include <set>
  6. #include <utility>
  7. #include <vector>
  8.  
  9. int main() {
  10.     int64_t stations, lineNum;
  11.     std::cin >> stations >> lineNum;
  12.     std::vector<std::set<int64_t>> lines(lineNum);
  13.     for (int64_t i = 0; i < lineNum; ++i) {
  14.         int64_t stInLine;
  15.         std::cin >> stInLine;
  16.         for (int64_t j = 0; j < stInLine; ++j) {
  17.             int64_t curStat;
  18.             std::cin >> curStat;
  19.             lines[i].insert(curStat);
  20.         }
  21.     }
  22.     int64_t from, to;
  23.     std::cin >> from >> to;
  24.     std::set<int64_t> reach = {from};
  25.     for (int64_t i = 0; i < lineNum; ++i) {
  26.         std::set<int64_t> newReach = reach;
  27.         for (int64_t j = 0; j < lineNum; j++) {
  28.             std::set<int64_t> inter;
  29.             std::set_intersection(std::begin(lines[j]), std::end(lines[j]), std::begin(reach),
  30.                                   std::end(reach), std::inserter(inter, std::begin(inter)));
  31.             if (!inter.empty()) {
  32.                 std::set_union(std::begin(lines[j]), std::end(lines[j]), std::begin(newReach),
  33.                                std::end(newReach), std::inserter(newReach, std::begin(newReach)));
  34.             }
  35.         }
  36.         reach = newReach;
  37.         if (reach.find(to) != std::end(reach)) {
  38.             std::cout << i << '\n';
  39.             return 0;
  40.         }
  41.     }
  42.     std::cout << -1 << '\n';
  43.     return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement