giveMeRadius

Given a connected undirected weighted graph (possibly with cycles) as its adjacency matrix, calculate its radius.

The radius of a graph is the minimum eccentricity of any vertex, where the eccentricity of a vertex v is the greatest distance between v and any other vertex.

For more information on how distances are calculated, check out this page.

Example

• For matrix = [[-1, -1, 1, 3], [-1, -1, -1, 2], [1, -1, -1, 7], [3, 2, 7, -1]] the output should be giveMeRadius(matrix) = 4.
  
  In this example eccentricity of the first vertex is 5, the second vertex is 6, the third vertex is 6, and the fourth vertex is 4. So, radius = min({5,6,6,4}) = 4.

Input/Output

• [execution time limit] 0.5 seconds (cpp)

• [input] array.array.integer matrix

  Adjacency matrix of the given graph, which is guaranteed to be symmetric. If matrix[i][j] > 0, the distance between vertices i and j is matrix[i][j]. Otherwise matrix[i][j] = -1, meaning that there’s no edge between vertices i and j.

  Constraints:
  
  2 ≤ matrix.length < 10,
  
  matrix[i][j] = matrix[j][i],
  
  matrix[i][i] = -1,
  
  matrix[0].length = matrix.length,
  
  -1 ≤ matrix[i][j] < 100.

• [output] integer

  • Radius of the given graph.