def multiply_adjacency_matrices(vertices, A, B):
  """
  'Multiply' two adjacency matrices where multiplication
  and addition are defined as:

  multiply: add values together
  add: take the minimum value

  Since normal multiplication for n x n matrices looks like:

  C[(i, j]] = sum([
    A[(i, k)] * B[(k, j)]
    for k in range(n)
  ])

  With our new definition of addition and multiplication,
  the operation becomes:

  C[(i, j)] = min([
    A[(i, k)] + B[(k, j)]
    for k in range(n)
  ])

  This new operation is the same as relaxing edges
  in the 1st DP approach.

  These operations with matrices form a semiring

  https://en.wikipedia.org/wiki/Semiring

  which is a mathematical structure like a ring but
  without the property of an additive inverse
  (min is not invertible).

  Complexity: O(v ** 3)

  """
  result = dict()
  for u in vertices:
    for v in vertices:
      result[(u, v)] = min([
        A[(u, x)] + B[(x, v)]
        for x in vertices
      ])
  return result