Time Cost

25min51s

Implementation

Note that using priority_queue with pair<int,int> will order elements by first then second. As a result, we should use [distance/time-cost, i] instead of [i, distance/time-cost]

Code

• My Solution

  class Solution {
    using PII = pair<int, int>;
  public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // maintain a vector d[] that represents the time from source to node i
        // maintain a priority queue that represents the minimum distance from source to node
  
        vector<vector<PII>> g(n + 1);
        for (auto& t: times) {
            g[t[0]].emplace_back(t[1], t[2]);
        }
  
        vector<long> d(n + 1, INT_MAX);
        d[k] = 0;
        vector<bool> v(n + 1, false);
        priority_queue<PII, vector<PII>, greater<PII>> q; // {d[i], i}
        q.emplace(0, k); // source to source timed 0
        int count = 0;
  
        while (!q.empty()) {
            int x = q.top().second;
            q.pop();
  
            if (v[x]) {
                continue;
            }
            v[x] = 1;
            count++;
  
            // from node x to other nodes
            for (auto& [i, t]: g[x]) {
                if (d[x] + t < d[i]) {
                    d[i] = d[x] + t;
                    q.emplace(d[i], i);
                }
            }
        }
  
        if (count != n) {
            return -1;
        }
  
        long result = 0;
        for (int i=1; i<d.size(); i++) {
            result = max(result, d[i]);
        }
  
        return result;
    }
  };