0743 - Network Delay Time (Medium)

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

class Solution {
public:
    template<typename T_pair, typename T_vector>
    void dijkstra(T_pair &g, T_vector &dist, int start) {
      priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
      dist[start] = 0;
      pq.push({start, 0});
      while (!pq.empty()) {
        auto [u_node, u_cost] = pq.top(); pq.pop();
        if (u_cost > dist[u_node]) continue;
        for (auto [v_node, v_cost] : g[u_node]) {
          if (dist[v_node] > dist[u_node] + v_cost) {
            dist[v_node] = dist[u_node] + v_cost;
            pq.push({v_node, dist[v_node]});
          }
        }
      }
    }

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pair<int, int>>> g(n + 1);
        for (auto x : times) g[x[0]].push_back({x[1], x[2]});
        vector<int> d(n + 1, 1e9);
        dijkstra(g, d, k);
        int ans = *max_element(d.begin() + 1, d.end());
        return ans == 1e9 ? -1 : ans;
    }
};

class Solution:
    # Time: O(E log V) where E is the number of Edges and V is the
    # number of vertices in the graph. We use a heap to maintain the
    # shortest paths of each node, and each edge is added at most once.
    # Results in O(E log E) operations, since E is at most O(V^2)
    # we can simplify: ElogV^2 -> 2ElogV -> ElogV
    # Space Complexity: O(V). Algorithm uses a set to track visited nodes
    # Have at most V elements, and a heap to store distances, which can
    # at most hold V elements.
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        # Build our adjacency list to traverse graph
        adj_list = [[] for _ in range(n + 1)]
        for (u,v,w) in times:
            adj_list[u].append((v,w))
        # initialize our heap, visited set.
        # Heap items (time, node) Where time is current time.
        heap = [(0,k)]
        visited = set()
        # Loop through all our values in the heap.
        while heap:
            # pop the current time and node
            t, node = heapq.heappop(heap)
            # Add node to our visited set, and check if we reached all
            visited.add(node)
            if len(visited) == n:
                # reached all nodes, return the time.
                return t
            # Loop through all nodes neighbours.
            for ni, ti in adj_list[node]:
                # If we haven't processed node before.
                if ni not in visited:
                    # Push time and node to heap.
                    # Times from our times list are times from previous
                    # node to now, and time we track is global time.
                    # So we add time to the node, with the global time.
                    heapq.heappush(heap, (t + ti, ni))
        # If we went through our whole heap without our visited ever
        # reaching n, it means we can't visit all nodes, so return -1.
        return -1

class Solution {
public:
    template<typename T_a3, typename T_vector>
    void bellman_ford(T_a3 &g, T_vector &dist, int src, int mx_edges) {
        // dist[i] : dist to reach node j using at most i edges from src
        dist[src] = 0;
        for (int i = 0; i <= mx_edges; i++) {
            T_vector ndist = dist;
            for (auto x : g) {
                auto [from, to, cost] = x;
                ndist[to] = min(ndist[to], dist[from] + cost);
            }
            dist = ndist;
        }
    }

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<array<int, 3>> g;
        vector<int> dist(n, 1e9);
        for (auto x : times) g.push_back({x[0] - 1, x[1] - 1, x[2]});
        bellman_ford(g, dist, k - 1, n);
        int mx = *max_element(dist.begin(), dist.end());
        return mx == 1e9 ? -1 : mx;
    }
};