美文网首页
743. 网络延迟时间

743. 网络延迟时间

作者: ZMT_sherry | 来源:发表于2018-09-22 18:28 被阅读0次

有 N 个网络节点,标记为 1 到 N。

给定一个列表 times,表示信号经过有向边的传递时间。 times[i] = (u, v, w),其中 u 是源节点,v 是目标节点, w 是一个信号从源节点传递到目标节点的时间。

现在,我们向当前的节点 K 发送了一个信号。需要多久才能使所有节点都收到信号?如果不能使所有节点收到信号,返回 -1。

注意:

N 的范围在 [1, 100] 之间。
K 的范围在 [1, N] 之间。
times 的长度在 [1, 6000] 之间。
所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 1 <= w <= 100。

import queue 
class Solution:
    
    def networkDelayTime(self, times, N, K):
        """
        :type times: List[List[int]]
        :type N: int
        :type K: int
        :rtype: int
        """
        dict={i:{} for i in range(1,N+1)}

        for i in times:
            u=i[0]
            v=i[1]
            w=i[2]
            dict[u][v]=w

        time_dict={i:-1 for i in range(1,N+1)}
        #start at k
        time_dict[K]=0
        q=queue.Queue()
        q.put(K)
        while not q.empty():
            x=q.get()
            sons_cost=tuple(dict[x].items())
            for (son,cost) in sons_cost:
                if time_dict[son]==-1:
                    time_dict[son]=time_dict[x]+cost
                    q.put(son)
                else:
                    if time_dict[son]>time_dict[x]+cost:
                        time_dict[son]=time_dict[x]+cost
                        q.put(son)
        if -1 not in list(time_dict.values()):
            return max(list(time_dict.values()))
        else:
            return -1
                    
        

相关文章

  • 743. 网络延迟时间

    有 N 个网络节点,标记为 1 到 N。 给定一个列表 times,表示信号经过有向边的传递时间。 times[i...

  • Leetcode每日一题(3)

    743. 网络延迟时间 有 N 个网络节点,标记为 1 到 N。 给定一个列表 times,表示信号经过有向边的传...

  • 743.网络延迟时间(Python)

    难度:★★★★☆类型:图方法:深度优先搜索 力扣链接请移步本题传送门[https://leetcode-cn.co...

  • Leetcode 743. 网络延迟时间(Dijkstra 算法

    问题描述 有 N 个网络节点,标记为 1 到 N。给定一个列表 times,表示信号经过有向边的传递时间。 tim...

  • 743. 网络延迟时间【深度优先搜索DFS】【超时】

    题目 思路 DFS;记录DFS到每个节点的时间arriveTime = make([]int, N+1, N+1)...

  • Day77 : 求网络延迟时间(没完全明白)

    Day77 : 求网络延迟时间 有 N 个网络节点,标记为 1 到 N。 给定一个列表 times,表示信号经过有...

  • 743. 晴无烟雨朦胧意,极尽相思念经年。 可续陈词书断笔,怎堪往事又翻篇。

  • 2020-09-04

    LayaBox小游戏 网页 极光推送 蜘蛛纸牌 延迟时间网络请求 第一个版本过了,第二次更新上传宣传图,人工审核三...

  • 深入理解Kafka(十) 延迟时间相关参数

    下面我们来介绍下Kafka怎么调优延迟时间相关的参数。对于kafka的不同组件,延迟时间的意义是不同的。对于pro...

  • DelayQueue源码分析

    延迟队列:往队列中放入的元素具有一定的延迟时间,延迟时间到期后,take或者poll方法才能获取到这些元素。先看以...

网友评论

      本文标题:743. 网络延迟时间

      本文链接:https://www.haomeiwen.com/subject/ssyxoftx.html