leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0815.cpp (1100B)

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 };