首页 > itarticle > [leetcode] problem 743 – network delay time

[leetcode] problem 743 – network delay time

admin 11月 13, 2020 0

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

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

Output: 2

Note

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

Code

public int (int[][] times, int N, int K) {
    int result = 0;
    List<int[]>[] graph = new List[N+1];
    int[] distance = new int[N+1];
    Queue<Integer> queue = new LinkedList<>();

    Arrays.fill(distance, Integer.MAX_VALUE);
    distance[K] = 0;
    queue.offer(K);

    for (int i = 0; i <= N; i++)
        graph[i] = new ArrayList<>();

    for (int[] time : times)
        graph[time[0]].add(new int[] {time[1], time[2]});

    while (!queue.isEmpty()) {
        int u = queue.poll();
        Set<Integer> visit = new HashSet<>();

        for (int[] edge : graph[u]) {
            int v = edge[0];
            int w = edge[1];

            if (distance[u] != Integer.MAX_VALUE && distance[v] > distance[u] + w) {
                distance[v] = distance[u] + w;

                if (visit.contains(v))
                    continue;

                queue.offer(v);
                visit.add(v);
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        if (distance[i] == Integer.MAX_VALUE)
            return -1;

        result = Math.max(result, distance[i]);
    }

    return result;
}