






import math
import sys



class 						lowerCamelCase   :







		'''simple docstring'''



		def __init__(							self     )			->							List[str]:
							UpperCAmelCase_					:   int   =		0
							UpperCAmelCase_					:   int   =		[]
							UpperCAmelCase_					:   int   =		{}  # To store the pos of node in array



		def       __UpperCAmelCase    (							self     )			->							str:
							return self.cur_size == 0



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase     )			->							str:
							UpperCAmelCase_					:   List[str]   =		self.left(_UpperCamelCase     )
							UpperCAmelCase_					:   Union[str, Any]   =		self.right(_UpperCamelCase     )
							if lc < self.cur_size and self.array(_UpperCamelCase     )[0] < self.array(_UpperCamelCase     )[0]:
												UpperCAmelCase_					:   Optional[Any]   =		lc
							else:
												UpperCAmelCase_					:   Optional[Any]   =		idx
							if rc < self.cur_size and self.array(_UpperCamelCase     )[0] < self.array(_UpperCamelCase     )[0]:
												UpperCAmelCase_					:   Any   =		rc
							if smallest != idx:
												self.swap(_UpperCamelCase       ,	_UpperCamelCase     )
												self.min_heapify(_UpperCamelCase     )



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase     )			->							Tuple:
							# Inserts a node into the Priority Queue
							UpperCAmelCase_					:   Any   =		self.cur_size
							self.cur_size += 1
							self.array.append((sys.maxsize, tup[1])     )
							self.decrease_key((sys.maxsize, tup[1])       ,	tup[0]     )



		def       __UpperCAmelCase    (							self     )			->							List[str]:
							# Removes and returns the min element at top of priority queue
							UpperCAmelCase_					:   Union[str, Any]   =		self.array[0][1]
							UpperCAmelCase_					:   Union[str, Any]   =		self.array[self.cur_size - 1]
							self.cur_size -= 1
							self.min_heapify(1     )
							del self.pos[min_node]
							return min_node



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase     )			->							Tuple:
							# returns the index of left child
							return 2 * i + 1



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase     )			->							str:
							# returns the index of right child
							return 2 * i + 2



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase     )			->							Optional[int]:
							# returns the index of parent
							return math.floor(i / 2     )



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase       ,	_UpperCamelCase     )			->							str:
							# swaps array elements at indices i and j
							# update the pos{}
							UpperCAmelCase_					:   str   =		j
							UpperCAmelCase_					:   Optional[int]   =		i
							UpperCAmelCase_					:   List[str]   =		self.array[i]
							UpperCAmelCase_					:   Tuple   =		self.array[j]
							UpperCAmelCase_					:   List[Any]   =		temp



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase       ,	_UpperCamelCase     )			->							Dict:
							UpperCAmelCase_					:   int   =		self.pos[tup[1]]
							# assuming the new_d is atmost old_d
							UpperCAmelCase_					:   List[Any]   =		(new_d, tup[1])
							while idx > 0 and self.array[self.par(_UpperCamelCase     )][0] > self.array[idx][0]:
												self.swap(_UpperCamelCase       ,	self.par(_UpperCamelCase     )     )
												UpperCAmelCase_					:   List[Any]   =		self.par(_UpperCamelCase     )





class 						lowerCamelCase   :







		'''simple docstring'''



		def __init__(							self       ,	_UpperCamelCase     )			->							Optional[int]:
							UpperCAmelCase_					:   Tuple   =		{}  # To store graph: u -> (v,w)
							UpperCAmelCase_					:   Tuple   =		num  # Number of nodes in graph
							# To store the distance from source vertex
							UpperCAmelCase_					:   Dict   =		[0] * self.num_nodes
							UpperCAmelCase_					:   List[str]   =		[-1] * self.num_nodes  # To store the path



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase       ,	_UpperCamelCase       ,	_UpperCamelCase     )			->							List[Any]:
							#  Edge going from node u to v and v to u with weight w
							# u (w)-> v, v (w) -> u
							# Check if u already in graph
							if u in self.adjList:
												self.adjList[u].append((v, w)     )
							else:
												UpperCAmelCase_					:   int   =		[(v, w)]

							# Assuming undirected graph
							if v in self.adjList:
												self.adjList[v].append((u, w)     )
							else:
												UpperCAmelCase_					:   Tuple   =		[(u, w)]



		def       __UpperCAmelCase    (							self     )			->							Any:
							# u -> v(w)
							for u in self.adjList:
												print(_UpperCamelCase       ,	'->'       ,	' -> '.join(str(f"{v}({w})"     ) for v, w in self.adjList[u]     )     )



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase     )			->							int:
							# Flush old junk values in par[]
							UpperCAmelCase_					:   Tuple   =		[-1] * self.num_nodes
							# src is the source node
							UpperCAmelCase_					:   Any   =		0
							UpperCAmelCase_					:   List[Any]   =		PriorityQueue()
							q.insert((0, src)     )  # (dist from src, node)
							for u in self.adjList:
												if u != src:
																	UpperCAmelCase_					:   Union[str, Any]   =		sys.maxsize  # Infinity
																	UpperCAmelCase_					:   Union[str, Any]   =		-1

							while not q.is_empty():
												UpperCAmelCase_					:   Tuple   =		q.extract_min()  # Returns node with the min dist from source
												# Update the distance of all the neighbours of u and
												# if their prev dist was INFINITY then push them in Q
												for v, w in self.adjList[u]:
																	UpperCAmelCase_					:   List[Any]   =		self.dist[u] + w
																	if self.dist[v] > new_dist:
																						if self.dist[v] == sys.maxsize:
																											q.insert((new_dist, v)     )
																						else:
																											q.decrease_key((self.dist[v], v)       ,	_UpperCamelCase     )
																						UpperCAmelCase_					:   Tuple   =		new_dist
																						UpperCAmelCase_					:   Dict   =		u

        # Show the shortest distances from src
							self.show_distances(_UpperCamelCase     )



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase     )			->							Any:
							print(f"Distance from node: {src}"     )
							for u in range(self.num_nodes     ):
												print(f"Node {u} has distance: {self.dist[u]}"     )



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase       ,	_UpperCamelCase     )			->							int:
							# To show the shortest path from src to dest
							# WARNING: Use it *after* calling dijkstra
							UpperCAmelCase_					:   Any   =		[]
							UpperCAmelCase_					:   int   =		0
							UpperCAmelCase_					:   Dict   =		dest
							# Backtracking from dest to src
							while self.par[temp] != -1:
												path.append(_UpperCamelCase     )
												if temp != src:
																	for v, w in self.adjList[temp]:
																						if v == self.par[temp]:
																											cost += w
																											break
												UpperCAmelCase_					:   Dict   =		self.par[temp]
							path.append(_UpperCamelCase     )
							path.reverse()

							print(f"----Path to reach {dest} from {src}----"     )
							for u in path:
												print(f"{u}"       ,	end=' '     )
												if u != dest:
																	print('-> '       ,	end=''     )

							print('\nTotal cost of path: '       ,	_UpperCamelCase     )


if __name__ == "__main__":
		__UpperCAmelCase										=		Graph(9)
		graph.add_edge(0, 1, 4)
		graph.add_edge(0, 7, 8)
		graph.add_edge(1, 2, 8)
		graph.add_edge(1, 7, 11)
		graph.add_edge(2, 3, 7)
		graph.add_edge(2, 8, 2)
		graph.add_edge(2, 5, 4)
		graph.add_edge(3, 4, 9)
		graph.add_edge(3, 5, 14)
		graph.add_edge(4, 5, 10)
		graph.add_edge(5, 6, 2)
		graph.add_edge(6, 7, 1)
		graph.add_edge(6, 8, 6)
		graph.add_edge(7, 8, 7)
		graph.show_graph()
		graph.dijkstra(0)
		graph.show_path(0, 4)

# OUTPUT
# 0 -> 1(4) -> 7(8)
# 1 -> 0(4) -> 2(8) -> 7(11)
# 7 -> 0(8) -> 1(11) -> 6(1) -> 8(7)
# 2 -> 1(8) -> 3(7) -> 8(2) -> 5(4)
# 3 -> 2(7) -> 4(9) -> 5(14)
# 8 -> 2(2) -> 6(6) -> 7(7)
# 5 -> 2(4) -> 3(14) -> 4(10) -> 6(2)
# 4 -> 3(9) -> 5(10)
# 6 -> 5(2) -> 7(1) -> 8(6)
# Distance from node: 0
# Node 0 has distance: 0
# Node 1 has distance: 4
# Node 2 has distance: 12
# Node 3 has distance: 19
# Node 4 has distance: 21
# Node 5 has distance: 11
# Node 6 has distance: 9
# Node 7 has distance: 8
# Node 8 has distance: 14
# ----Path to reach 4 from 0----
# 0 -> 7 -> 6 -> 5 -> 4
# Total cost of path:  21














from __future__ import annotations

from typing import Any




def   lowercase__   (  *__snake_case					:							list[list[int]]						):


					'''simple docstring'''


					if all(_check_not_integer(__snake_case						) for m in matrix_s						):
										for i in matrix_s[1:]:
															_verify_matrix_sizes(matrix_s[0]  , __snake_case						)
										return [[sum(__snake_case						) for t in zip(*__snake_case						)] for m in zip(*__snake_case						)]
					raise TypeError('Expected a matrix, got int/list instead'						)




def   lowercase__   (  __snake_case					:							list[list[int]]  , __snake_case					:							list[list[int]]						):


					'''simple docstring'''


					if (
					    _check_not_integer(__snake_case						)
					    and _check_not_integer(__snake_case						)
					    and _verify_matrix_sizes(__snake_case  , __snake_case						)
					):
										return [[i - j for i, j in zip(*__snake_case						)] for m in zip(__snake_case  , __snake_case						)]
					raise TypeError('Expected a matrix, got int/list instead'						)




def   lowercase__   (  __snake_case					:							list[list[int]]  , __snake_case					:							int | float						):


					'''simple docstring'''


					return [[x * n for x in row] for row in matrix]




def   lowercase__   (  __snake_case					:							list[list[int]]  , __snake_case					:							list[list[int]]						):


					'''simple docstring'''


					if _check_not_integer(__snake_case						) and _check_not_integer(__snake_case						):
										UpperCAmelCase_ ,						UpperCAmelCase_					:   str   =		_verify_matrix_sizes(__snake_case  , __snake_case						)

					if cols[0] != rows[1]:
										UpperCAmelCase_					:   Dict   =		(
										    'Cannot multiply matrix of dimensions '
										    F"({rows[0]},{cols[0]}) and ({rows[1]},{cols[1]})"
										)
										raise ValueError(__snake_case						)
					return [
					    [sum(m * n for m, n in zip(__snake_case  , __snake_case						)						) for j in zip(*__snake_case						)] for i in matrix_a
					]




def   lowercase__   (  __snake_case					:							int						):


					'''simple docstring'''


					UpperCAmelCase_					:   Optional[Any]   =		int(__snake_case						)
					return [[int(row == column						) for column in range(__snake_case						)] for row in range(__snake_case						)]




def   lowercase__   (  __snake_case					:							list[list[int]]  , __snake_case					:							bool = True						):


					'''simple docstring'''


					if _check_not_integer(__snake_case						):
										if return_map:
															return map(__snake_case  , zip(*__snake_case						)						)
										else:
															return list(map(__snake_case  , zip(*__snake_case						)						)						)
					raise TypeError('Expected a matrix, got int/list instead'						)




def   lowercase__   (  __snake_case					:							list[list[int]]  , __snake_case					:							int  , __snake_case					:							int						):


					'''simple docstring'''


					UpperCAmelCase_					:   Any   =		matrix[:row] + matrix[row + 1 :]
					return [row[:column] + row[column + 1 :] for row in minor]




def   lowercase__   (  __snake_case					:							list[list[int]]						):


					'''simple docstring'''


					if len(__snake_case						) == 1:
										return matrix[0][0]

					return sum(
					    x * determinant(minor(__snake_case  , 0  , __snake_case						)						) * (-1) ** i
					    for i, x in enumerate(matrix[0]						)						)




def   lowercase__   (  __snake_case					:							list[list[int]]						):


					'''simple docstring'''


					UpperCAmelCase_					:   Optional[int]   =		determinant(__snake_case						)
					if det == 0:
										return None

					UpperCAmelCase_					:   List[str]   =		[
					    [determinant(minor(__snake_case  , __snake_case  , __snake_case						)						) for j in range(len(__snake_case						)						)]
					    for i in range(len(__snake_case						)						)
					]

					UpperCAmelCase_					:   List[str]   =		[
					    [x * (-1) ** (row + col) for col, x in enumerate(matrix_minor[row]						)]
					    for row in range(len(__snake_case						)						)
					]
					UpperCAmelCase_					:   Tuple   =		list(transpose(__snake_case						)						)
					return scalar_multiply(__snake_case  , 1 / det						)




def   lowercase__   (  __snake_case					:							list[list[int]]						):


					'''simple docstring'''


					return not isinstance(__snake_case  , __snake_case						) and not isinstance(matrix[0]  , __snake_case						)




def   lowercase__   (  __snake_case					:							list[list[int]]						):


					'''simple docstring'''


					return len(__snake_case						), len(matrix[0]						)




def   lowercase__   (  __snake_case					:							list[list[int]]  , __snake_case					:							list[list[int]]						):


					'''simple docstring'''


					UpperCAmelCase_					:   Optional[Any]   =		_shape(__snake_case						) + _shape(__snake_case						)
					if shape[0] != shape[3] or shape[1] != shape[2]:
										UpperCAmelCase_					:   Optional[int]   =		(
										    'operands could not be broadcast together with shape '
										    F"({shape[0], shape[1]}), ({shape[2], shape[3]})"
										)
										raise ValueError(__snake_case						)
					return (shape[0], shape[2]), (shape[1], shape[3])




def   lowercase__   (  ):


					'''simple docstring'''


					UpperCAmelCase_					:   Tuple   =		[[12, 10], [3, 9]]
					UpperCAmelCase_					:   Optional[int]   =		[[3, 4], [7, 4]]
					UpperCAmelCase_					:   List[str]   =		[[11, 12, 13, 14], [21, 22, 23, 24], [31, 32, 33, 34], [41, 42, 43, 44]]
					UpperCAmelCase_					:   str   =		[[3, 0, 2], [2, 0, -2], [0, 1, 1]]
					print(F"Add Operation, {add(__snake_case  , __snake_case						) = } \n"						)
					print(
					    F"Multiply Operation, {multiply(__snake_case  , __snake_case						) = } \n"  , )
					print(F"Identity: {identity(5						)}\n"						)
					print(F"Minor of {matrix_c} = {minor(__snake_case  , 1  , 2						)} \n"						)
					print(F"Determinant of {matrix_b} = {determinant(__snake_case						)} \n"						)
					print(F"Inverse of {matrix_d} = {inverse(__snake_case						)}\n"						)


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		main()






