from __future__ import annotations
class   UpperCAmelCase__				:


	"""simple docstring"""







	def __init__(			self       ,     _SCREAMING_SNAKE_CASE )    ->	None:
							a_							:			Any     		=					vertices
							a_							:			Any     		=					[[0] * vertices for _ in range(_SCREAMING_SNAKE_CASE )]







	def       A    (			self       ,     _SCREAMING_SNAKE_CASE )    ->	None:
							print("Vertex \t Distance from Source" )
							for vertex in range(self.vertices ):
													print(_SCREAMING_SNAKE_CASE       ,     "\t\t"       ,     distances_from_source[vertex] )







	def       A    (			self       ,     _SCREAMING_SNAKE_CASE       ,     _SCREAMING_SNAKE_CASE )    ->	int:
							a_							:			Dict     		=					1E7
							a_							:			Union[str, 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:
																			a_							:			int     		=					distances_from_source[vertex]
																			a_							:			Dict     		=					vertex
							return min_index







	def       A    (			self       ,     _SCREAMING_SNAKE_CASE )    ->	None:
							a_							:			Tuple     		=					[int(1E7 )] * self.vertices  # distances from the source
							a_							:			str     		=					0
							a_							:			Union[str, Any]     		=					[False] * self.vertices

							for _ in range(self.vertices ):
													a_							:			Union[str, Any]     		=					self.minimum_distance(_SCREAMING_SNAKE_CASE       ,     _SCREAMING_SNAKE_CASE )
													a_							:			List[str]     		=					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]
																			):
																									a_							:			Any     		=					distances[u] + self.graph[u][v]

							self.print_solution(_SCREAMING_SNAKE_CASE )


if __name__ == "__main__":
				UpperCamelCase     					=     Graph(9)
				UpperCamelCase     					=     [
				    [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"""






def  lowerCAmelCase_      (_SCREAMING_SNAKE_CASE	:str  )				-> int:
						a_							:			Optional[int]     		=					0
						for letter in data:
												a_							:			Union[str, Any]     		=					(hash_ << 4) + ord(_SCREAMING_SNAKE_CASE  )
												a_							:			Optional[int]     		=					hash_ & 0xf000_0000
												if x != 0:
																		hash_ ^= x >> 24
												hash_ &= ~x
						return hash_


if __name__ == "__main__":
				import doctest

				doctest.testmod()




