leetcode

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

0743.cpp (765B)

      1 class Solution {
      2     typedef pair<int, int> edge;
      3 
      4   public:
      5     int networkDelayTime(vector<vector<int>> &times, int n, int k) {
      6         vector<vector<edge>> adj(n + 1, vector<edge>());
      7         for (auto &p : times)
      8             adj[p[0]].push_back({p[2], p[1]});
      9 
     10         priority_queue<edge, vector<edge>, greater<edge>> st;
     11         unordered_set<int> us;
     12 
     13         int time = 0;
     14         st.push({0, k});
     15         while (!st.empty()) {
     16             auto [t, root] = st.top();
     17             st.pop();
     18             if (us.count(root)) continue;
     19             time = t;
     20             us.insert(root);
     21             for (auto &[time, dest] : adj[root])
     22                 if (!us.count(dest)) st.push({t + time, dest});
     23         }
     24         return us.size() == n ? time : -1;
     25     }
     26 };