743. Network Delay Time

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

Note:

1. N will be in the range [1, 100].
2. K will be in the range [1, N].
3. The length of times will be in the range [1, 6000].
4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

struct comp {

    bool operator()(pair<int, int>& a, pair<int, int>& b) {

        return a.second > b.second;

    }

};

class Solution {

public:

    int networkDelayTime(vector<vector<int>>& times, int N, int K) {

        unordered_map<int, set<pair<int, int>>> graph;

        generate(graph, N, times);

        return bfs(graph, K);

    }

    

    void generate(unordered_map<int, set<pair<int, int>>>& graph,

                 int N, vector<vector<int>>& times) {

        for (auto edge : times) {

            graph[edge[0]].insert({edge[1], edge[2]});

        }

        for (int i = 1; i <= N; i++) {

            if (!graph.count(i)) {

                graph[i] = {};

            }

        }

    }

    

    int bfs(unordered_map<int, set<pair<int, int>>>& graph,

           int K) {

        if (!graph.count(K)) {

            return -1;

        }

        

        int node_count = 1, ans = 0, total = 0;

        priority_queue<pair<int, int>, vector<pair<int, int>>, comp> q;

        q.push({K,0});

        unordered_map<int,int> dist;

        dist[K] = 0;

        while (!q.empty()) {

            pair<int, int> node = q.top(); q.pop();

            for (auto neighbor: graph[node.first]) {

                if (!dist.count(neighbor.first) ||

                    dist[neighbor.first] > node.second + neighbor.second) {

                    q.push({neighbor.first, node.second + neighbor.second});

                    dist[neighbor.first] = node.second + neighbor.second;

                }

            }

        }

        if (dist.size() != graph.size()) {

            return -1;

        }

        for (auto entry : dist) {

            ans = max(ans, entry.second);

        }

        return ans;

    }

};

=========== Simple queue works too. May be redundant paths are not there.====

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        int res = 0;
        unordered_map<int, vector<pair<int, int>>> edges;
        vector<int> dist(N + 1, INT_MAX);
        queue<int> q{{K}};
        dist[K] = 0;
        for (auto e : times) edges[e[0]].push_back({e[1], e[2]});
        while (!q.empty()) {
            int u = q.front(); q.pop();
            unordered_set<int> visited;
            for (auto e : edges[u]) {
                int v = e.first, w = e.second;
                if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    if (visited.count(v)) continue;
                    visited.insert(v);
                    q.push(v);
                }
            }
        }
        for (int i = 1; i <= N; ++i) {
            res = max(res, dist[i]);
        }
        return res == INT_MAX ? -1 : res;
    }
};

====================

C++ / Bellman-Ford

Time complexity: O(ne)

Space complexity: O(n)







1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17



// Author: Huahua

// Runtime: 92 ms

class Solution {

public:

    int networkDelayTime(vector<vector<int>>& times, int N, int K) {

        constexpr int MAX_TIME = 101 * 100;

        vector<int> dist(N, MAX_TIME);

        dist[K - 1] = 0;

        for (int i = 1; i < N; ++i)

            for (const auto& time : times) {

                int u = time[0] - 1, v = time[1] - 1, w = time[2];

                dist[v] = min(dist[v], dist[u] + w);

            }

        int max_dist = *max_element(dist.begin(), dist.end());

        return max_dist == MAX_TIME ? -1 : max_dist;

    }

};