...

Code Block | ||||||
---|---|---|---|---|---|---|

| ||||||

class Solution: def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int: graph = {} for i in range(1, N + 1): graph.setdefault(i, []) for node in times: graph[node[0]].append([node[1], node[2]]) dist = {node: float('inf') for node in range(1, N + 1)} def dfs(node, depth): if depth >= dist[node]: return dist[node] = depth for n, w in graph[node]: dfs(n, depth + w) dfs(K, 0) ans = max(dist.values()) return ans if ans < float('inf') else -1 |

Code Block | ||||||
---|---|---|---|---|---|---|

| ||||||

```
class Solution:
def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
graph = collections.defaultdict(dict)
for i in range(1, N + 1):
graph[i] = {}
for v, n, w in times:
graph[v][n] = w
infinity = float("inf")
costs = {}
for e in graph:
if e not in costs:
if e == K:
costs[e] = 0
for se in graph[e]:
costs[se] = graph[e][se]
else:
costs[e] = infinity
visited = []
node = self.find_lowest_cost_node(costs, visited)
while node is not None:
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys():
new_cost = cost + neighbors[n]
if costs[n] > new_cost:
costs[n] = new_cost
visited.append(node)
node = self.find_lowest_cost_node(costs, visited)
ans = max(costs.values())
return ans if ans < float('inf') else -1
def find_lowest_cost_node(self, costs, visited):
lowest_cost = float("inf")
lowest_cost_node = None
for node in costs:
cost = costs[node]
if cost < lowest_cost and node not in visited:
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node
``` |