


'''simple docstring'''




from sklearn.metrics import mean_absolute_error

import datasets


__lowercase	:   str   		=					"""\
@article{scikit-learn,
 title={Scikit-learn: Machine Learning in {P}ython},
 author={Pedregosa, F. and Varoquaux, G. and Gramfort, A. and Michel, V.
         and Thirion, B. and Grisel, O. and Blondel, M. and Prettenhofer, P.
         and Weiss, R. and Dubourg, V. and Vanderplas, J. and Passos, A. and
         Cournapeau, D. and Brucher, M. and Perrot, M. and Duchesnay, E.},
 journal={Journal of Machine Learning Research},
 volume={12},
 pages={2825--2830},
 year={2011}
}
"""

__lowercase	:   Dict   		=					"""\
Mean Absolute Error (MAE) is the mean of the magnitude of difference between the predicted and actual
values.
"""


__lowercase	:   Optional[int]   		=					"""
Args:
    predictions: array-like of shape (n_samples,) or (n_samples, n_outputs)
        Estimated target values.
    references: array-like of shape (n_samples,) or (n_samples, n_outputs)
        Ground truth (correct) target values.
    sample_weight: array-like of shape (n_samples,), default=None
        Sample weights.
    multioutput: {\"raw_values\", \"uniform_average\"} or array-like of shape (n_outputs,), default=\"uniform_average\"
        Defines aggregating of multiple output values. Array-like value defines weights used to average errors.

                 \"raw_values\" : Returns a full set of errors in case of multioutput input.

                 \"uniform_average\" : Errors of all outputs are averaged with uniform weight.

Returns:
    mae : mean absolute error.
        If multioutput is \"raw_values\", then mean absolute error is returned for each output separately. If multioutput is \"uniform_average\" or an ndarray of weights, then the weighted average of all output errors is returned.
        MAE output is non-negative floating point. The best value is 0.0.
Examples:

    >>> mae_metric = datasets.load_metric(\"mae\")
    >>> predictions = [2.5, 0.0, 2, 8]
    >>> references = [3, -0.5, 2, 7]
    >>> results = mae_metric.compute(predictions=predictions, references=references)
    >>> print(results)
    {'mae': 0.5}

    If you're using multi-dimensional lists, then set the config as follows :

    >>> mae_metric = datasets.load_metric(\"mae\", \"multilist\")
    >>> predictions = [[0.5, 1], [-1, 1], [7, -6]]
    >>> references = [[0, 2], [-1, 2], [8, -5]]
    >>> results = mae_metric.compute(predictions=predictions, references=references)
    >>> print(results)
    {'mae': 0.75}
    >>> results = mae_metric.compute(predictions=predictions, references=references, multioutput='raw_values')
    >>> print(results)
    {'mae': array([0.5, 1. ])}
"""





@datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION     , _KWARGS_DESCRIPTION )
class _snake_case (			datasets.Metric ):
							"""simple docstring"""





							def 		__SCREAMING_SNAKE_CASE( self						)  ->int:



											"""simple docstring"""







											return datasets.MetricInfo(
											    description=_DESCRIPTION      ,					citation=_CITATION      ,					inputs_description=_KWARGS_DESCRIPTION      ,					features=datasets.Features(self._get_feature_types()						)      ,					reference_urls=[
											        "https://scikit-learn.org/stable/modules/generated/sklearn.metrics.mean_absolute_error.html"
											    ]      ,					)







							def 		__SCREAMING_SNAKE_CASE( self						)  ->Tuple:



											"""simple docstring"""







											if self.config_name == "multilist":
															return {
															    "predictions": datasets.Sequence(datasets.Value("float"						)						),
															    "references": datasets.Sequence(datasets.Value("float"						)						),
															}
											else:
															return {
															    "predictions": datasets.Value("float"						),
															    "references": datasets.Value("float"						),
															}







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A      ,					__A=None      ,					__A="uniform_average"						)  ->Any:



											"""simple docstring"""







											__lowerCamelCase		:   int           =       mean_absolute_error(__A      ,					__A      ,					sample_weight=__A      ,					multioutput=__A						)

											return {"mae": mae_score}









'''simple docstring'''




import math
import sys





class _snake_case :
							"""simple docstring"""





							def __init__( self						)  ->int:



											"""simple docstring"""







											__lowerCamelCase		:   int           =       0
											__lowerCamelCase		:   str           =       []
											__lowerCamelCase		:   int           =       {}  # To store the pos of node in array







							def 		__SCREAMING_SNAKE_CASE( self						)  ->Union[str, Any]:



											"""simple docstring"""







											return self.cur_size == 0







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->Union[str, Any]:



											"""simple docstring"""







											__lowerCamelCase		:   Any           =       self.left(__A						)
											__lowerCamelCase		:   Any           =       self.right(__A						)
											if lc < self.cur_size and self.array(__A						)[0] < self.array(__A						)[0]:
															__lowerCamelCase		:   Dict           =       lc
											else:
															__lowerCamelCase		:   List[Any]           =       idx
											if rc < self.cur_size and self.array(__A						)[0] < self.array(__A						)[0]:
															__lowerCamelCase		:   List[str]           =       rc
											if smallest != idx:
															self.swap(__A      ,					__A						)
															self.min_heapify(__A						)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->str:



											"""simple docstring"""







											__lowerCamelCase		:   Optional[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 		__SCREAMING_SNAKE_CASE( self						)  ->int:



											"""simple docstring"""







											__lowerCamelCase		:   Tuple           =       self.array[0][1]
											__lowerCamelCase		:   str           =       self.array[self.cur_size - 1]
											self.cur_size -= 1
											self.min_heapify(1						)
											del self.pos[min_node]
											return min_node







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->int:



											"""simple docstring"""







											return 2 * i + 1







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->Optional[Any]:



											"""simple docstring"""







											return 2 * i + 2







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->Tuple:



											"""simple docstring"""







											return math.floor(i / 2						)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A						)  ->List[Any]:



											"""simple docstring"""







											__lowerCamelCase		:   Union[str, Any]           =       j
											__lowerCamelCase		:   str           =       i
											__lowerCamelCase		:   Dict           =       self.array[i]
											__lowerCamelCase		:   Union[str, Any]           =       self.array[j]
											__lowerCamelCase		:   str           =       temp







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A						)  ->Optional[Any]:



											"""simple docstring"""







											__lowerCamelCase		:   str           =       self.pos[tup[1]]
											# assuming the new_d is atmost old_d
											__lowerCamelCase		:   Union[str, Any]           =       (new_d, tup[1])
											while idx > 0 and self.array[self.par(__A						)][0] > self.array[idx][0]:
															self.swap(__A      ,					self.par(__A						)						)
															__lowerCamelCase		:   List[Any]           =       self.par(__A						)





class _snake_case :
							"""simple docstring"""





							def __init__( self      ,					__A						)  ->Any:



											"""simple docstring"""







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







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A      ,					__A						)  ->Optional[Any]:



											"""simple docstring"""







											if u in self.adjList:
															self.adjList[u].append((v, w)						)
											else:
															__lowerCamelCase		:   Dict           =       [(v, w)]

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







							def 		__SCREAMING_SNAKE_CASE( self						)  ->Tuple:



											"""simple docstring"""







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







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->int:



											"""simple docstring"""







											__lowerCamelCase		:   List[str]           =       [-1] * self.num_nodes
											# src is the source node
											__lowerCamelCase		:   str           =       0
											__lowerCamelCase		:   int           =       PriorityQueue()
											q.insert((0, src)						)  # (dist from src, node)
											for u in self.adjList:
															if u != src:
																			__lowerCamelCase		:   List[Any]           =       sys.maxsize  # Infinity
																			__lowerCamelCase		:   Dict           =       -1

											while not q.is_empty():
															__lowerCamelCase		:   int           =       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]:
																			__lowerCamelCase		:   str           =       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)      ,					__A						)
																							__lowerCamelCase		:   str           =       new_dist
																							__lowerCamelCase		:   Tuple           =       u

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







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->int:



											"""simple docstring"""







											print(f'Distance from node: {src}'						)
											for u in range(self.num_nodes						):
															print(f'Node {u} has distance: {self.dist[u]}'						)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A						)  ->Optional[int]:



											"""simple docstring"""







											__lowerCamelCase		:   List[Any]           =       []
											__lowerCamelCase		:   Tuple           =       0
											__lowerCamelCase		:   List[str]           =       dest
											# Backtracking from dest to src
											while self.par[temp] != -1:
															path.append(__A						)
															if temp != src:
																			for v, w in self.adjList[temp]:
																							if v == self.par[temp]:
																											cost += w
																											break
															__lowerCamelCase		:   int           =       self.par[temp]
											path.append(__A						)
											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: "      ,					__A						)


if __name__ == "__main__":
				__lowercase	:   Optional[Any]   		=					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





