743. Network Delay Time

题目来源：

https://leetcode.com/problems/network-delay-time/

自我感觉难度/真实难度：

题意：

分析：

自己的代码：

class Solution:

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

        """

        :type times: List[List[int]]

        :type N: int

        :type K: int

        :rtype: int

        """

        K-=1

        nodes=collections.defaultdict(list)

        for u,v,w in times:

            nodes[u-1].append((v-1,w))

        dist=[float('inf')]*N

        dist[K]=0

        done=set()

        for _ in range(N):

            smallest=min((d,i) for (i,d) in enumerate(dist) if i not in done)[1]

            for v,w in nodes[smallest]:

                if v not in done and dist[smallest]+w<dist[v]:

                    dist[v]=dist[smallest]+w

            done.add(smallest)

        return -1 if float('inf') in dist else max(dist)

代码效率/结果：

Runtime: 152 ms, faster than 83.77% of Python3 online submissions forNetwork Delay Time.

优秀代码：

class Solution:

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

        """

        :type times: List[List[int]]

        :type N: int

        :type K: int

        :rtype: int

        """

        h = [(0, K)]

        res = 0

        reached = set()

        d = {}

        for u, v, w in times:

            if u not in d:

                d[u] = []

            d[u].append([v, w])

        while h:

            t, n = heapq.heappop(h)

            if n not in reached:

                res = t

                reached.add(n)

                if n in d:

                    for v, w in d[n]:

                        if v not in reached:

                            heapq.heappush(h, [t + w, v])

        if len(reached) < N:

            return -1

        return res

优秀的结题报告，提供了三种超级棒的解答方法：https://blog.csdn.net/fuxuemingzhu/article/details/82862769

第一次写图的代码，其实草稿纸推一推，发现也不是特别的难，不要畏惧

代码效率/结果：

自己优化后的代码：

反思改进策略：

1.对heapq的模块不熟悉，后面几天着重练习一下堆栈这一块的练习

2.对dijstra算法不熟悉，希望把上面的模块背出来

float('inf')表示正无穷

float('-inf')表示负无穷

dist=[float('inf')]*N

初始化List简单的办法

巴特西

743. Network Delay Time

题目来源：

自我感觉难度/真实难度：

题意：

分析：

自己的代码：

代码效率/结果：

优秀代码：

代码效率/结果：

自己优化后的代码：

反思改进策略：

最新文章

热门文章