leetcode

0 class Solution {

1 public:

2 int numBusesToDestination(const vector<vector<int>> &routes, int source, int target) const {

3 if (source == target) return 0;

4

5 unordered_map<int, vector<int>> adj;

6 for (int i = 0; i < routes.size(); i++) {

7 for (const int n : routes[i])

8 adj[n].push_back(i);

9 }

10

11 if (!adj.count(target)) return -1;

12

13 unordered_set<int> used;

14 queue<int> q;

15

16 q.push(source);

17 for (int lvl = 1; !q.empty(); lvl++) {

18 for (int k = q.size(); k > 0; k--) {

19 const int crnt = q.front();

20 q.pop();

21 for (const int r : adj[crnt]) {

22 if (used.count(-r)) continue;

23 used.insert(-r);

24 for (const int v : routes[r]) {

25 if (used.count(v)) continue;

26 if (v == target) return lvl;

27 used.insert(v);

28 q.push(v);

29 }

30 }

31 }

32 }

33

34 return -1;

35 }

36 };