


from __future__ import annotations


class       __lowerCAmelCase       :






  """simple docstring"""





  def __init__(       self    :    str      ,			_lowerCAmelCase    :    int					)				->	None:




     """simple docstring"""
     snake_case_         =   vertices
     snake_case_         =   [[0] * vertices for _ in range(_lowerCAmelCase					)]



  def    lowerCAmelCase__					(       self    :    Tuple      ,			_lowerCAmelCase    :    list[int]					)				->	None:




     """simple docstring"""
     print("Vertex \t Distance from Source"					)
     for vertex in range(self.vertices					):
        print(_lowerCAmelCase      ,			"\t\t"      ,			distances_from_source[vertex]					)



  def    lowerCAmelCase__					(       self    :    int      ,			_lowerCAmelCase    :    list[int]      ,			_lowerCAmelCase    :    list[bool]					)				->	int:




     """simple docstring"""
     snake_case_         =   1e7
     snake_case_         =   0

     # Search not nearest vertex not in the shortest path tree
     for vertex in range(self.vertices					):
        if distances_from_source[vertex] < minimum and visited[vertex] is False:
           snake_case_         =   distances_from_source[vertex]
           snake_case_         =   vertex
     return min_index



  def    lowerCAmelCase__					(       self    :    Optional[int]      ,			_lowerCAmelCase    :    int					)				->	None:




     """simple docstring"""
     snake_case_         =   [int(1e7					)] * self.vertices  # distances from the source
     snake_case_         =   0
     snake_case_         =   [False] * self.vertices

     for _ in range(self.vertices					):
        snake_case_         =   self.minimum_distance(_lowerCAmelCase      ,			_lowerCAmelCase					)
        snake_case_         =   True

        # Update dist value of the adjacent vertices
        # of the picked vertex only if the current
        # distance is greater than new distance and
        # the vertex in not in the shortest path tree
        for v in range(self.vertices					):
           if (
               self.graph[u][v] > 0
               and visited[v] is False
               and distances[v] > distances[u] + self.graph[u][v]
           ):
              snake_case_         =   distances[u] + self.graph[u][v]

     self.print_solution(_lowerCAmelCase					)


if __name__ == "__main__":
   SCREAMING_SNAKE_CASE		:Optional[Any]											=       Graph(9)
   SCREAMING_SNAKE_CASE		:Any											=       [
       [0, 4, 0, 0, 0, 0, 0, 8, 0],
       [4, 0, 8, 0, 0, 0, 0, 11, 0],
       [0, 8, 0, 7, 0, 4, 0, 0, 2],
       [0, 0, 7, 0, 9, 14, 0, 0, 0],
       [0, 0, 0, 9, 0, 10, 0, 0, 0],
       [0, 0, 4, 14, 10, 0, 2, 0, 0],
       [0, 0, 0, 0, 0, 2, 0, 1, 6],
       [8, 11, 0, 0, 0, 0, 1, 0, 7],
       [0, 0, 2, 0, 0, 0, 6, 7, 0],
   ]
   graph.dijkstra(0)








from __future__ import annotations



def      _lowerCAmelCase  (							lowerCAmelCase_							:int							)->list[int]:
   '''simple docstring'''






   assert (
       isinstance(lowerCAmelCase_						,  lowerCAmelCase_							) and mask > 0
   ), F'''mask needs to be positive integer, your input {mask}'''
   snake_case_         =   []
   snake_case_         =   mask

   while submask:
      all_submasks.append(lowerCAmelCase_							)
      snake_case_         =   (submask - 1) & mask

   return all_submasks


if __name__ == "__main__":
   import doctest

   doctest.testmod()




