743. Network Delay Time

Posted on Edited on In

743. Network Delay Time

Description

Difficulty: Medium

Related Topics: Depth-First Search, Breadth-First Search, Graph, Heap (Priority Queue), Shortest Path

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 0 <= wi <= 100
  • All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

Hints/Notes

  • 2023/09/05
  • Dijkstra algorithm
  • The dijkstra algorithm always try to find the shortest route from the root
  • 0x3F’s solution(checked)

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    vector<vector<vector<int>>> graph;
    vector<int> distances;
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        graph = vector<vector<vector<int>>>(n + 1, vector<vector<int>>());
        distances = vector<int>(n + 1, INT_MAX);
        buildGraph(times);
        pq.push({0, k});
        distances[k] = 0;

        while (!pq.empty()) {
            vector<int> point = pq.top();
            pq.pop();

            int distance = point[0];
            int to = point[1];
            // it's possible that one route with more time is pushed before
            // a better route, so the following condition would shortcut that
            if (distance > distances[to]) {
                continue;
            }

            for (auto edge : graph[to]) {
                int dis_next = edge[1] + distance;
                // we only add new path if there's better route
                if (distances[edge[0]] > dis_next) {
                    distances[edge[0]] = dis_next;
                    pq.push({dis_next, edge[0]});
                }
            }
        }

        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (distances[i] == INT_MAX) {
                return -1;
            }
            res = max(res, distances[i]);
        }

        return res;
    }

    void buildGraph(vector<vector<int>>& times) {
        for (auto time : times) {
            int from = time[0];
            int to = time[1];
            int dis = time[2];
            graph[from].push_back({to, dis});
        }
    }
};