
"""simple docstring"""






def __A						(   a_ :							List[str]		,		a_ :							Optional[Any]     )->							Union[str, Any]:




		'''simple docstring'''






		print('''\nThe shortest path matrix using Floyd Warshall algorithm\n'''     )
		for i in range(a_     ):
				for j in range(a_     ):
						if dist[i][j] != float('''inf'''     ):
								print(int(dist[i][j]     )		,		end='''\t'''     )
						else:
								print('''INF'''		,		end='''\t'''     )
				print()





def __A						(   a_ :							Optional[int]		,		a_ :							Union[str, Any]     )->							Dict:




		'''simple docstring'''






		SCREAMING_SNAKE_CASE       :     Optional[int]				= [[float('''inf'''     ) for _ in range(a_     )] for _ in range(a_     )]

		for i in range(a_     ):
				for j in range(a_     ):
						SCREAMING_SNAKE_CASE       :     List[str]				= graph[i][j]

						# check vertex k against all other vertices (i, j)
		for k in range(a_     ):
				# looping through rows of graph array
				for i in range(a_     ):
						# looping through columns of graph array
						for j in range(a_     ):
								if (
								    dist[i][k] != float('''inf'''     )
								    and dist[k][j] != float('''inf'''     )
								    and dist[i][k] + dist[k][j] < dist[i][j]
								):
										SCREAMING_SNAKE_CASE       :     Tuple				= dist[i][k] + dist[k][j]

		_print_dist(a_		,		a_     )
		return dist, v


if __name__ == "__main__":
					lowerCamelCase__ :       Dict						     =			int(input("Enter number of vertices: "))
					lowerCamelCase__ :       Tuple						     =			int(input("Enter number of edges: "))

					lowerCamelCase__ :       str						     =			[[float("inf") for i in range(v)] for j in range(v)]

					for i in range(v):
										lowerCamelCase__ :       str						     =			0.0

										# src and dst are indices that must be within the array size graph[e][v]
										# failure to follow this will result in an error
					for i in range(e):
										print("\nEdge ", i + 1)
										lowerCamelCase__ :       List[Any]						     =			int(input("Enter source:"))
										lowerCamelCase__ :       List[str]						     =			int(input("Enter destination:"))
										lowerCamelCase__ :       Optional[int]						     =			float(input("Enter weight:"))
										lowerCamelCase__ :       Tuple						     =			weight

					floyd_warshall(graph, v)

					# Example Input
					# Enter number of vertices: 3
					# Enter number of edges: 2

					# # generated graph from vertex and edge inputs
					# [[inf, inf, inf], [inf, inf, inf], [inf, inf, inf]]
					# [[0.0, inf, inf], [inf, 0.0, inf], [inf, inf, 0.0]]

					# specify source, destination and weight for edge #1
					# Edge  1
					# Enter source:1
					# Enter destination:2
					# Enter weight:2

					# specify source, destination and weight for edge #2
					# Edge  2
					# Enter source:2
					# Enter destination:1
					# Enter weight:1

					# # Expected Output from the vertice, edge and src, dst, weight inputs!!
					# 0		INF	INF
					# INF	0	2
					# INF	1	0







"""simple docstring"""






def __A						(   a_ :							list		,		a_ :							int		,		a_ :							int = 0		,		a_ :							int = 0     )->							int:




		'''simple docstring'''






		SCREAMING_SNAKE_CASE       :     str				= right or len(a_     ) - 1
		if left > right:
				return -1
		elif list_data[left] == key:
				return left
		elif list_data[right] == key:
				return right
		else:
				return search(a_		,		a_		,		left + 1		,		right - 1     )


if __name__ == "__main__":
					import doctest

					doctest.testmod()





