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.
Solution1: floyd(TLE)
class Solution: def networkDelayTime(self, times, N, K): """ :type times: List[List[int]] :type N: int :type K: int :rtype: int """ ans = [[float('inf') for i in range(N)] for _ in range(N)] for time in times: ans[time[0]-1][time[1]-1] = time[2] for i in range(N): ans[i][i] = 0 for k in range(N): for i in range(N): for j in range(N): ans[i][j] = min(ans[i][j],ans[i][k]+ans[k][j]) return -1 if float('inf') in ans[K-1] else max(ans[K-1]) Solution2:Bellman-Ford(TLE)
class Solution: def networkDelayTime(self, times, N, K): """ :type times: List[List[int]] :type N: int :type K: int :rtype: int """ ans = [float('inf') for _ in range(N)] ans[K-1] = 0 for i in range(N): for time in times: u,v,w = time[0]-1,time[1]-1,time[2] ans[v] = min(ans[v],ans[u] + w) return -1 if float('inf') in ans else max(ans) Solution3:dijkstra
from collections import defaultdictclass Solution: def networkDelayTime(self, times, N, K): """ :type times: List[List[int]] :type N: int :type K: int :rtype: int """ K -= 1 nodes = defaultdict(list) for u,v,w in times: nodes[u-1].append((v-1,w)) ans = [float('inf') for _ in range(N)] ans[K] = 0 s = set() for _ in range(N): smallest = min((d,i) for (i,d) in enumerate(ans) if i not in s)[1] for v,w in nodes[smallest]: if v not in s and ans[smallest]+w < ans[v]: ans[v] = ans[smallest] + w s.add(smallest) return -1 if float('inf') in ans else max(ans)