LWC 62:743. Network Delay Time

LWC 62:743. Network Delay Time

传送门:743. Network Delay Time

Problem:

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.

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 1 <= w <= 100.

思路: 求从某个结点k出发到任意结点的距离,在这些距离中找最大值即可。实际上该题是求解任意两个结点之间的最短路径,先采用Dijkstra算法实现一波。最短路径的相关知识可以参考【挑战程序竞赛系列(11):2.5最短路径

Java版:

    class Edge{
        int from;
        int to;
        int weight;

        Edge(int from, int to, int weight){
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    class Node implements Comparable<Node>{

        int v;
        int dist;

        Node(int v, int dist){
            this.v = v;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node that) {
            return this.dist - that.dist;
        }
    }

    public int networkDelayTime(int[][] times, int N, int K) {

        int n = times.length;
        List<Edge>[] graph = new ArrayList[N];

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

        for (int i = 0; i < n; ++i) {
            int from   = times[i][0];
            int to     = times[i][1];
            int weight = times[i][2];
            from --;
            to --;
            graph[from].add(new Edge(from, to, weight));
        }

        int ans = 0;
        boolean[] vis = new boolean[N];

        Queue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(K - 1, 0));

        int[] dist = new int[N];
        Arrays.fill(dist, 0x3f3f3f3f);

        while (!queue.isEmpty()) {
            Node now = queue.poll();
            for (Edge e : graph[now.v]) {
                if (!vis[e.from]) {
                    Node nxt = new Node(e.to, now.dist + e.weight);
                    dist[e.to] = Math.min(dist[e.to], nxt.dist);
                    queue.offer(nxt);
                }
            }
            vis[now.v] = true;
        }

        for (int i = 0; i < N; ++i) {
            if (i == K - 1) continue;
            ans = Math.max(ans, dist[i]);
        }


        return ans >= 0x3f3f3f3f ? -1 : ans;
    }

当然计算任意结点之间的最短距离可以采用warshallFloyd算法,代码如下:

     public int networkDelayTime(int[][] times, int N, int K) {
         int INF = 0x3f3f3f3f;
         int[][] dist = new int[N][N];

         for (int i = 0; i < N; ++i) {
             for (int j = 0; j < N; ++j) {
                 dist[i][j] = INF;
             }
         }

         for (int[] time : times) {
             int from = time[0];
             int to   = time[1];
             int cost = time[2];
             from --;
             to --;
             dist[from][to] = cost;
         }

         for (int k = 0; k < N; ++k) {
             for (int i = 0; i < N; ++i) {
                 for (int j = 0; j < N; ++j) {
                     dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                 }
             }
         }

         int ans = 0;
         for (int i = 0; i < N; ++i) {
             if (i ==  K - 1) continue;
             ans = Math.max(ans, dist[K - 1][i]);
         }

         return ans >= INF ? -1 : ans;
     }

warshallFloyd算法的正确性详见知乎高票回答【Floyd算法为什么把k放在最外层?

Python版:

    def networkDelayTime(self, times, N, K):
        """
        :type times: List[List[int]]
        :type N: int
        :type K: int
        :rtype: int
        """
        INF = 0x3f3f3f3f
        dist = [[INF] * N for _ in range(N)]

        for time in times:
            u = time[0]
            v = time[1]
            w = time[2]
            dist[u - 1][v - 1] = w

        for k in xrange(N):
            for i in xrange(N):
                for j in xrange(N):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

        ans = 0
        for i in range(N):
            if (i == K - 1): continue
            else:
                ans = max(ans, dist[K - 1][i])

        return -1 if ans >= INF else ans

Python Dijkstra 版:

    def networkDelayTime(self, times, N, K):
        import heapq

        """
        :type times: List[List[int]]
        :type N: int
        :type K: int
        :rtype: int
        """
        pq = []
        INF = float('inf')
        dist = [INF] * N

        graph = [[] for _ in range(N)]

        for time in times:
            graph[time[0] - 1].append((time[1] - 1, time[2]))

        heapq.heappush(pq, (0, K - 1))
        dist[K - 1] = 0

        while len(pq):
            cur = heapq.heappop(pq)
            for to, cost in graph[cur[1]]:
                if (dist[to] > dist[cur[1]] + cost):
                    dist[to] = cost + dist[cur[1]]
                    heapq.heappush(pq, (dist[to], to))

        ans = 0
        for i in range(N):
            if i == K - 1:
                continue
            else:
                ans = max(ans, dist[i])

        return -1 if ans >= INF else ans

知道为什么Dijkstra没有发明warshallFloyd么?因为他的名字是D”ijk”stra而不是D”kij”stra,哈哈!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏测试开发架构之路

程序员面试50题(2)—二元查找树的后序遍历结果[数据结构]

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、8,由于这一...

2616
来自专栏和蔼的张星的图像处理专栏

60. 搜索插入位置二分查找__细节

给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。

1023
来自专栏java工会

java冒泡排序和快速排序

2063
来自专栏Java开发者杂谈

算法之数组和问题

算法题之数组和求解 数组和问题 ​ 加上给定一个数组和值x。设计一个算法使得如果数组中存在两个元素的和为x,则输出两个元素的值组成的数组(不区分先后),否则输出...

3708
来自专栏数据结构与算法

3110 二叉堆练习3

3110 二叉堆练习3 时间限制: 3 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 给定N...

2825
来自专栏数据结构与算法

26:统计满足条件的4位数个数

26:统计满足条件的4位数个数 总时间限制: 1000ms 内存限制: 65536kB描述 给定若干个四位数,求出其中满足以下条件的数的个数:  个位数上的...

4034
来自专栏小小挖掘机

Numpy基础知识点汇总

1、概述 Numpy是高性能科学计算和数据分析的基础包,它的部分功能如下: 1)ndarray,一个具有矢量算术运算和复杂广播能力的快速且节省空间的多维数组。 ...

2904
来自专栏简书专栏

Numpy入门2

标题中的英文首字母大写比较规范,但在python实际使用中均为小写。 2018年7月26日笔记

1103
来自专栏Felix的技术分享

【LeetCode】Letter Combinations of a Phone Number

1714
来自专栏赵俊的Java专栏

奇偶分割数组

1324

扫码关注云+社区