1
# Runtime: 2578 ms (Top 92.45%) | Memory: 69.3 MB (Top 19.78%)
2
class Solution:
3
    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
4

5
        # Build Adjency List
6
        adjList = defaultdict(list)
7

8
        for source, target in edges:
9
            adjList[source].append(target)
10
            adjList[target].append(source)
11

12
        # BFS to get the shortest route from node to master.
13
        shortest = {}
14
        queue = deque([(0, 0)])
15
        seen = set()
16
        while queue:
17
            currPos, currDist = queue.popleft()
18

19
            if currPos in seen:
20
                continue
21
            seen.add(currPos)
22
            shortest[currPos] = currDist
23

24
            for nei in adjList[currPos]:
25
                queue.append((nei, currDist + 1))
26

27
        # Calculate answer using shortest paths.
28
        ans = 0
29
        for index in range(1, len(patience)):
30
            resendInterval = patience[index]
31

32
            # The server will stop sending requests after it's been sent to the master node and back.
33
            shutOffTime = shortest[index] * 2
34

35
            # shutOffTime-1 == Last second the server can send a re-request.
36
            lastSecond = shutOffTime - 1
37

38
            # Calculate the last time a packet is actually resent.
39
            lastResentTime = (lastSecond // resendInterval) * resendInterval
40

41
            # At the last resent time, the packet still must go through 2 more cycles to the master node and back.
42
            lastPacketTime = lastResentTime + shutOffTime
43

44
            ans = max(lastPacketTime, ans)
45

46
        # Add +1, the current answer is the last time the packet is recieved by the target server (still active).
47
        # We must return the first second the network is idle, therefore + 1
48
        return ans + 1