leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0815.cpp (1100B)

      1 class Solution {
      2   public:
      3     int numBusesToDestination(const vector<vector<int>> &routes, int source, int target) const {
      4         if (source == target) return 0;
      5 
      6         unordered_map<int, vector<int>> adj;
      7         for (int i = 0; i < routes.size(); i++) {
      8             for (const int n : routes[i])
      9                 adj[n].push_back(i);
     10         }
     11 
     12         if (!adj.count(target)) return -1;
     13 
     14         unordered_set<int> used;
     15         queue<int> q;
     16 
     17         q.push(source);
     18         for (int lvl = 1; !q.empty(); lvl++) {
     19             for (int k = q.size(); k > 0; k--) {
     20                 const int crnt = q.front();
     21                 q.pop();
     22                 for (const int r : adj[crnt]) {
     23                     if (used.count(-r)) continue;
     24                     used.insert(-r);
     25                     for (const int v : routes[r]) {
     26                         if (used.count(v)) continue;
     27                         if (v == target) return lvl;
     28                         used.insert(v);
     29                         q.push(v);
     30                     }
     31                 }
     32             }
     33         }
     34 
     35         return -1;
     36     }
     37 };