743. Network Delay Time

1. Question

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 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:

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

Example 2:

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

Example 3:

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

2. 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.)

3. References

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/network-delay-time 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

4. Solutions

  1. Folyd

    class Solution {
        public int networkDelayTime(int[][] times, int n, int k) {
            final int MAX = 999999;
    
            int[][] res = new int[n + 1][n + 1];
            for (int[] re : res) {
                Arrays.fill(re, MAX);
            }
            for (int i = 1; i <= n; i++) {
                res[i][i] = 0;
            }
    
            for (int i = 0; i < times.length; i++) {
                res[times[i][0]][times[i][1]] = times[i][2];
            }
    
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    for (int l = 1; l <= n; l++) {
                        if (res[j][l] > res[j][i] + res[i][l]) {
                            res[j][l] = res[j][i] + res[i][l];
                        }
                    }
                }
            }
    
            int max = -1;
    
            for (int i = 1; i <= n; i++) {
                if (k == i) {
                    continue;
                }
                if (MAX == res[k][i]) {
                    max = -1;
                    break;
                }
                if (res[k][i] > max) {
                    max = res[k][i];
                }
            }
    
            return max;
        }
    }
    
Copyright © rootwhois.cn 2021-2022 all right reserved,powered by GitbookFile Modify: 2022-05-18 16:24:00

results matching ""

    No results matching ""