
"""simple docstring"""







import heapq
def       __UpperCAmelCase		(		a_      :		Tuple     ,	a_      :		Any     ,	a_      :		Any					)  ->							Dict:
   _UpperCAmelCase 						=       [(0, start)]  # cost from start node,end node
   _UpperCAmelCase 						=       set()
   while heap:
      ((_UpperCAmelCase)						,				(_UpperCAmelCase)) 						=       heapq.heappop(A__					)
      if u in visited:
         continue
      visited.add(A__					)
      if u == end:
         return cost
      for v, c in graph[u]:
         if v in visited:
            continue
         _UpperCAmelCase 						=       cost + c
         heapq.heappush(A__     ,	(next_item, v)					)
   return -1


SCREAMING_SNAKE_CASE_  					= {
    '''A''': [['''B''', 2], ['''C''', 5]],
    '''B''': [['''A''', 2], ['''D''', 3], ['''E''', 1], ['''F''', 1]],
    '''C''': [['''A''', 5], ['''F''', 3]],
    '''D''': [['''B''', 3]],
    '''E''': [['''B''', 4], ['''F''', 3]],
    '''F''': [['''C''', 3], ['''E''', 3]],
}
SCREAMING_SNAKE_CASE_  					= {
    '''B''': [['''C''', 1]],
    '''C''': [['''D''', 1]],
    '''D''': [['''F''', 1]],
    '''E''': [['''B''', 1], ['''F''', 3]],
    '''F''': [],
}
SCREAMING_SNAKE_CASE_  					= {
    '''B''': [['''C''', 1]],
    '''C''': [['''D''', 1]],
    '''D''': [['''F''', 1]],
    '''E''': [['''B''', 1], ['''G''', 2]],
    '''F''': [],
    '''G''': [['''F''', 1]],
}

SCREAMING_SNAKE_CASE_  					= dijkstra(G, 'E', 'C')
print(short_distance)  # E -- 3 --> F -- 3 --> C == 6

SCREAMING_SNAKE_CASE_  					= dijkstra(Ga, 'E', 'F')
print(short_distance)  # E -- 3 --> F == 3

SCREAMING_SNAKE_CASE_  					= dijkstra(Ga, 'E', 'F')
print(short_distance)  # E -- 2 --> G -- 1 --> F == 3

if __name__ == "__main__":
  import doctest

  doctest.testmod()




"""simple docstring"""




SCREAMING_SNAKE_CASE_  :      Optional[int]							=      {0: [1, 2], 1: [0, 3], 2: [0], 3: [1], 4: [5, 6], 5: [4, 6], 6: [4, 5]}

SCREAMING_SNAKE_CASE_  :      str							=      {0: [1, 2, 3], 1: [0, 3], 2: [0], 3: [0, 1], 4: [], 5: []}



def 						UpperCAmelCase__ (					A__						,     A__						,     A__ )   ->   list:




   """simple docstring"""
   lowerCamelCase__						       =      True
   lowerCamelCase__						       =      []

   for neighbour in graph[vert]:
      if not visited[neighbour]:
         connected_verts += dfs(A__						,     A__						,     A__ )

   return [vert, *connected_verts]



def 						UpperCAmelCase__ (					A__ )   ->   list:




   """simple docstring"""
   lowerCamelCase__						       =      len(A__ )
   lowerCamelCase__						       =      graph_size * [False]
   lowerCamelCase__						       =      []

   for i in range(A__ ):
      if not visited[i]:
         lowerCamelCase__						       =      dfs(A__						,     A__						,     A__ )
         components_list.append(A__ )

   return components_list


if __name__ == "__main__":
     import doctest

     doctest.testmod()




