FilesExpand file tree

 main

/

743_Network_Delay_Time.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

21 lines (16 loc) · 665 Bytes

 main

/

743_Network_Delay_Time.py

Copy path

Top

File metadata and controls

• Code
• Blame

21 lines (16 loc) · 665 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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

from collections import deque

class Solution:

def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:

self.graph = [deque() for i in range(N+1)]

for u, v, w in times:

self.graph[u].append((v, w))

self.dist = [float('inf')] * (N+1)

self.dfs(K)

tot = max(self.dist[1:])

return tot if tot != float('inf') else -1

def dfs(self, v, elapsed=0):

if elapsed >= self.dist[v]: return

self.dist[v] = elapsed

for neighbor, weight in self.graph[v]:

self.dfs(neighbor, elapsed + weight)