目录

0743:网络延迟时间(★)

力扣第 743 题

题目

n 个网络节点,标记为 1n

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

现在,从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号?如果不能使所有节点收到信号,返回 -1

示例 1:

输入:times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出:2

示例 2:

输入:times = [[1,2,1]], n = 2, k = 1
输出:1

示例 3:

输入:times = [[1,2,1]], n = 2, k = 2
输出:-1

提示:

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 0 <= wi <= 100
  • 所有 (ui, vi) 对都 互不相同(即,不含重复边)

相似问题:

分析

典型的单源最短路径问题,可以用 dijkstra 算法。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        g = [[] for _ in range(n)]
        for u,v,w in times:
            g[u-1].append((v-1,w))
        d = [inf]*n
        d[k-1] = 0
        pq = [(0,k-1)]
        while pq:
            w,u = heappop(pq)
            if w>d[u]:
                continue
            for v,w2 in g[u]:
                if w+w2<d[v]:
                    d[v] = w+w2
                    heappush(pq,(w+w2,v))
        res = max(d)
        return res if res<inf else -1

时间 O(M*logM),65 ms

*附加

本题数据量很小,可以练习各种最短路算法。

#1 Floyd

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        f = [[inf]*n for _ in range(n)]
        for i in range(n):
            f[i][i] = 0
        for u, v, w in times:
            f[u-1][v-1] = w
        for x,i,j in product(range(n),range(n),range(n)):
            f[i][j] = min(f[i][j],f[i][x]+f[x][j])
        res = max(f[k-1])
        return res if res<inf else -1

时间 O(N^3),761 ms

#2 Bellman-Ford

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        d = [inf]*n
        d[k-1] = 0
        for _ in range(n-1):
            flag = True
            for u,v,w in times:
                if d[u-1]+w<d[v-1]:
                    d[v-1] = d[u-1]+w
                    flag = False
            if flag:
                break
        res = max(d)
        return res if res<inf else -1

时间 O(M*N),63 ms

#3 SPFA

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        g = [[] for _ in range(n)]
        for u,v,w in times:
            g[u-1].append((v-1,w))
        d = [inf]*n
        d[k-1] = 0
        Q, vis = deque([k-1]), {k-1}
        while Q:
            u = Q.popleft()
            vis.remove(u)
            for v,w in g[u]:
                if d[u]+w<d[v]:
                    d[v] = d[u]+w
                    if v not in vis:
                        vis.add(v)
                        Q.append(v)
        res = max(d)
        return res if res<inf else -1

时间 O(M*N),52 ms

#4 Dijkstra 朴素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        g = [[] for _ in range(n)]
        for u,v,w in times:
            g[u-1].append((v-1,w))
        d = [inf]*n
        d[k-1] = 0
        Q = set(range(n))
        while Q:
            u = min(Q,key=lambda i:d[i])
            Q.remove(u)
            for v,w in g[u]:
                d[v] = min(d[v],d[u]+w)
        res = max(d)
        return res if res<inf else -1

时间 O(N^2),66 ms