#2039

The Time When the Network Becomes Idle

specialist · 795 · lc medium +31 · verified · 55.4% accepted · 742 likes · top 49%

⚑ Multi-Source BFS

Description

A network has n servers labeled 0 to n - 1, connected by undirected edges edges (each edge allows instant message passing in one second). Server 0 is the master; all others are data servers. At second 0, every data server sends its message to the master via the shortest path. The master replies instantly along the same path. If a data server i has not received a reply and patience[i] seconds have elapsed since its last send, it resends the message — repeating every patience[i] seconds until the reply arrives. Return the earliest second at which the network becomes completely idle (no messages in transit or arriving).

Example 1:

Input: edges = [[0,1],[1,2]], patience = [0,2,1]
Output: 8
Explanation:
At (the beginning of) second 0,
- Data server 1 sends its message (denoted 1A) to the master server.
- Data server 2 sends its message (denoted 2A) to the master server.

Example 2:

At second 1,
- Message 1A arrives at the master server. Master server processes message 1A instantly and sends a reply 1A back.
- Server 1 has not received any reply. 1 second (1 < patience[1] = 2) elapsed since this server has sent the message, therefore it does not resend the message.
- Server 2 has not received any reply. 1 second (1 == patience[2] = 1) elapsed since this server has sent the message, therefore it resends the message (denoted 2B).

Example 3:

At second 2,
- The reply 1A arrives at server 1. No more resending will occur from server 1.
- Message 2A arrives at the master server. Master server processes message 2A instantly and sends a reply 2A back.
- Server 2 resends the message (denoted 2C).
...
At second 4,
- The reply 2A arrives at server 2. No more resending will occur from server 2.
...
At second 7, reply 2D arrives at server 2.

Example 4:

Starting from the beginning of the second 8, there are no messages passing between servers or arriving at servers.
This is the time when the network becomes idle.

Example 5:

Input: edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]
Output: 3
Explanation: Data servers 1 and 2 receive a reply back at the beginning of second 2.
From the beginning of the second 3, the network becomes idle.

Code

1
2
3