



from __future__ import annotations

class     SCREAMING_SNAKE_CASE:







	"""simple docstring"""






	def __init__(						self      :					int		,      __snake_case      :					int		)      ->		None:
								UpperCAmelCase			:	Tuple										=		vertices
								UpperCAmelCase			:	List[str]										=		[[0] * vertices for _ in range(__snake_case		)]







	def 					A     (						self      :					Tuple		,      __snake_case      :					list[int]		)      ->		None:
								print('''Vertex \t Distance from Source'''		)
								for vertex in range(self.vertices		):
															print(__snake_case		,      '''\t\t'''		,      distances_from_source[vertex]		)







	def 					A     (						self      :					List[str]		,      __snake_case      :					list[int]		,      __snake_case      :					list[bool]		)      ->		int:
								UpperCAmelCase			:	Tuple										=		1E7
								UpperCAmelCase			:	List[Any]										=		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:
																						UpperCAmelCase			:	Union[str, Any]										=		distances_from_source[vertex]
																						UpperCAmelCase			:	Union[str, Any]										=		vertex
								return min_index







	def 					A     (						self      :					List[Any]		,      __snake_case      :					int		)      ->		None:
								UpperCAmelCase			:	List[Any]										=		[int(1E7		)] * self.vertices  # distances from the source
								UpperCAmelCase			:	Optional[int]										=		0
								UpperCAmelCase			:	str										=		[False] * self.vertices

								for _ in range(self.vertices		):
															UpperCAmelCase			:	Tuple										=		self.minimum_distance(__snake_case		,      __snake_case		)
															UpperCAmelCase			:	Any										=		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]
																						):
																													UpperCAmelCase			:	Optional[Any]										=		distances[u] + self.graph[u][v]

								self.print_solution(__snake_case		)


if __name__ == "__main__":
						UpperCamelCase__:       Union[str, Any]							     =      Graph(9)
						UpperCamelCase__:       List[str]							     =      [
						    [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)










'''simple docstring'''






from __future__ import annotations


def 			snake_case_					( _lowerCAmelCase  :						list[int]       ,				_lowerCAmelCase  :						int  )				->       list[int]:
							UpperCAmelCase			:	dict[int, int]										=		{}
							for index, val in enumerate(_lowerCAmelCase  ):
														UpperCAmelCase			:	Tuple										=		target - val
														if compl in chk_map:
																					return [chk_map[compl], index]
														UpperCAmelCase			:	Any										=		index
							return []


if __name__ == "__main__":
						import doctest

						doctest.testmod()
						print(F"{two_sum([2, 7, 11, 15], 9) = }")





