


from __future__ import annotations

class      __snake_case				:
					def __init__(						self       :						Any	,      _lowerCAmelCase       :						int  )							->					None:



											'''simple docstring'''





											__magic_name__					=      vertices
											__magic_name__					=      [[0] * vertices for _ in range(_lowerCAmelCase  )]
					def 	a			(						self       :						List[Any]	,      _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 	a			(						self       :						Tuple	,      _lowerCAmelCase       :						list[int]	,      _lowerCAmelCase       :						list[bool]  )							->					int:



											'''simple docstring'''





											__magic_name__					=      1E7
											__magic_name__					=      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:
																							__magic_name__					=      distances_from_source[vertex]
																							__magic_name__					=      vertex
											return min_index







					def 	a			(						self       :						Any	,      _lowerCAmelCase       :						int  )							->					None:



											'''simple docstring'''





											__magic_name__					=      [int(1E7  )] * self.vertices  # distances from the source
											__magic_name__					=      0
											__magic_name__					=      [False] * self.vertices

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

											self.print_solution(_lowerCAmelCase  )


if __name__ == "__main__":
					UpperCamelCase			:					Optional[Any]         =							Graph(9)
					UpperCamelCase			:					Dict         =							[
					    [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 itertools import count
from math import asin, pi, sqrt
def 				UpperCamelCase_	(					__snake_case      :    float  )->   float:




						'''simple docstring'''
						return (
						    (1 - 2 * point) * sqrt(point - point**2  ) + 2 * point + asin(sqrt(1 - point  )  )
						) / 4
def 				UpperCamelCase_	(					__snake_case      :    int  )->   float:




						'''simple docstring'''
						__magic_name__					=      (circles_number + 1 - sqrt(2 * circles_number  )) / (
						    2 * (circles_number**2 + 1)
						)
						__magic_name__					=      circles_number * intersection_y

						__magic_name__					=      intersection_x * intersection_y / 2
						__magic_name__					=      circle_bottom_arc_integral(
						    1 / 2  ) - circle_bottom_arc_integral(__snake_case  )

						return triangle_area + concave_region_area
def 				UpperCamelCase_	(					__snake_case      :    float = 1 / 10_00  )->   int:




						'''simple docstring'''
						__magic_name__					=      (1 - pi / 4) / 4

						for n in count(1  ):
												if concave_triangle_area(__snake_case  ) / l_section_area < fraction:
																		return n

						return -1


if __name__ == "__main__":
					print(f'''{solution() = }''')

