# Page History

## Key

• This line was removed.
• Formatting was changed.

...

Code Block
language py network_delay_time완전탐색 : 8464 ms true
```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].append([node, node])

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
language py 다익스트라 : 452ms true
```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```