
'''simple docstring'''



import itertools
from dataclasses import dataclass
from typing import Optional

import pandas as pd
import pyarrow as pa

import datasets
from datasets.table import table_cast




@dataclass
class   UpperCAmelCase_					(		datasets.BuilderConfig			):






						'''simple docstring'''






						_lowercase		:				Optional[datasets.Features]									=       None






class   UpperCAmelCase_					(		datasets.ArrowBasedBuilder			):






						'''simple docstring'''






						_lowercase		:				Union[str, Any]									=       PandasConfig




						def  _lowercase     ( self				):

												"""simple docstring"""



												return datasets.DatasetInfo(features=self.config.features				)




						def  _lowercase     ( self   ,       _lowercase				):

												"""simple docstring"""



												if not self.config.data_files:
																		raise ValueError(F'At least one data file must be specified, but got data_files={self.config.data_files}'				)
												_lowerCAmelCase  						=			dl_manager.download_and_extract(self.config.data_files				)
												if isinstance(_lowercase   ,       (str, list, tuple)				):
																		_lowerCAmelCase  						=			data_files
																		if isinstance(_lowercase   ,       _lowercase				):
																								_lowerCAmelCase  						=			[files]
																		# Use `dl_manager.iter_files` to skip hidden files in an extracted archive
																		_lowerCAmelCase  						=			[dl_manager.iter_files(_lowercase				) for file in files]
																		return [datasets.SplitGenerator(name=datasets.Split.TRAIN   ,       gen_kwargs={"""files""": files}				)]
												_lowerCAmelCase  						=			[]
												for split_name, files in data_files.items():
																		if isinstance(_lowercase   ,       _lowercase				):
																								_lowerCAmelCase  						=			[files]
																		# Use `dl_manager.iter_files` to skip hidden files in an extracted archive
																		_lowerCAmelCase  						=			[dl_manager.iter_files(_lowercase				) for file in files]
																		splits.append(datasets.SplitGenerator(name=_lowercase   ,       gen_kwargs={"""files""": files}				)				)
												return splits




						def  _lowercase     ( self   ,       _lowercase				):

												"""simple docstring"""



												if self.config.features is not None:
																		# more expensive cast to support nested features with keys in a different order
																		# allows str <-> int/float or str to Audio for example
																		_lowerCAmelCase  						=			table_cast(_lowercase   ,       self.config.features.arrow_schema				)
												return pa_table




						def  _lowercase     ( self   ,       _lowercase				):

												"""simple docstring"""



												for i, file in enumerate(itertools.chain.from_iterable(_lowercase				)				):
																		with open(_lowercase   ,       """rb"""				) as f:
																								_lowerCAmelCase  						=			pa.Table.from_pandas(pd.read_pickle(_lowercase				)				)
																								yield i, self._cast_table(_lowercase				)


'''simple docstring'''



import heapq as hq
import math
from collections.abc import Iterator




class   UpperCAmelCase_					:






						'''simple docstring'''






						def __init__( self   ,       _lowercase				):

												"""simple docstring"""



												_lowerCAmelCase  						=			str(id_				)
												_lowerCAmelCase  						=			None
												_lowerCAmelCase  						=			None
												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			{}  # {vertex:distance}




						def __lt__( self   ,       _lowercase				):

												"""simple docstring"""



												return self.key < other.key




						def __repr__( self				):

												"""simple docstring"""



												return self.id




						def  _lowercase     ( self   ,       _lowercase				):

												"""simple docstring"""



												self.neighbors.append(_lowercase				)




						def  _lowercase     ( self   ,       _lowercase   ,       _lowercase				):

												"""simple docstring"""



												_lowerCAmelCase  						=			weight






def A				(__lowerCamelCase				:List[Any]			,     __lowerCamelCase				:Union[str, Any]			,     __lowerCamelCase				:Dict			,     __lowerCamelCase				:Optional[int]		):
						# add the neighbors:
						graph[a - 1].add_neighbor(graph[b - 1]		)
						graph[b - 1].add_neighbor(graph[a - 1]		)
						# add the edges:
						graph[a - 1].add_edge(graph[b - 1]			,     __lowerCamelCase		)
						graph[b - 1].add_edge(graph[a - 1]			,     __lowerCamelCase		)


def A				(__lowerCamelCase				:list			,     __lowerCamelCase				:Vertex		):
						_lowerCAmelCase  						=			[]
						for u in graph:
												_lowerCAmelCase  						=			math.inf
												_lowerCAmelCase  						=			None
						_lowerCAmelCase  						=			0
						_lowerCAmelCase  						=			graph[:]
						while q:
												_lowerCAmelCase  						=			min(__lowerCamelCase		)
												q.remove(__lowerCamelCase		)
												for v in u.neighbors:
																		if (v in q) and (u.edges[v.id] < v.key):
																								_lowerCAmelCase  						=			u
																								_lowerCAmelCase  						=			u.edges[v.id]
						for i in range(1			,     len(__lowerCamelCase		)		):
												a.append((int(graph[i].id		) + 1, int(graph[i].pi.id		) + 1)		)
						return a


def A				(__lowerCamelCase				:list			,     __lowerCamelCase				:Vertex		):
						for u in graph:
												_lowerCAmelCase  						=			math.inf
												_lowerCAmelCase  						=			None
						_lowerCAmelCase  						=			0

						_lowerCAmelCase  						=			list(__lowerCamelCase		)
						hq.heapify(__lowerCamelCase		)

						while h:
												_lowerCAmelCase  						=			hq.heappop(__lowerCamelCase		)
												for v in u.neighbors:
																		if (v in h) and (u.edges[v.id] < v.key):
																								_lowerCAmelCase  						=			u
																								_lowerCAmelCase  						=			u.edges[v.id]
																								hq.heapify(__lowerCamelCase		)

						for i in range(1			,     len(__lowerCamelCase		)		):
												yield (int(graph[i].id		) + 1, int(graph[i].pi.id		) + 1)


def A				():
						pass


if __name__ == "__main__":
						import doctest

						doctest.testmod()
