How Long Until Every Server Hears the Broadcast

Implement broadcastTime

A message is broadcast from one server in a network of servers joined by one-way links, each with a positive delay, given as an n × n matrix. Every server forwards the message immediately along all of its links. Find when the last server receives it, or -1 if some server is never reached.

This is a single-source shortest path problem; the answer is the largest of the shortest arrival times.

Example 1:

Input: links = [[0,2,5,0,0,0],[0,0,1,6,0,0],[0,0,0,2,0,9],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,0,0,0,0]], src = 0

Output: 12

Example 2:

Input: links = [[0,4],[0,0]], src = 1

Output: -1

Example 3:

Input: links = [[0]], src = 0

Output: 0

+ 14 hidden test cases run on Submit.

Constraints:

  • ●1 ≤ n ≤ 8 servers numbered 0 … n-1; links is an n × n matrix: links[u][v] = 0 means no direct link from u to v, links[u][v] = t (1 ≤ t ≤ 20) means a one-way link that delivers a message from u to v in t time units
  • ●links[u][u] = 0; every server that receives the message forwards it immediately on all its outgoing links
  • ●0 ≤ src < n is the server that sends the broadcast at time 0
  • ●Return the time at which the LAST server receives the message, or -1 if some server never receives it

links =

[[0,2,5,0,0,0], [0,0,1,6,0,0], [0,0,0,2,0,9], [0,0,0,0,1,0], [0,0,0,0,0,0], [0,0,0,0,0,0]]

src =

0