code: 
  
  
  
  
  
  from typing import List
  
  from packaging import version
  from sklearn.metrics import fa_score
  
  import datasets
  from datasets.config import PY_VERSION
  
  
  if PY_VERSION < version.parse("3.8"):
     import importlib_metadata
  else:
     import importlib.metadata as importlib_metadata
  
  
  # TODO(Patrick/Anton)
  lowerCAmelCase_   =   "\\n"
  
  lowerCAmelCase_   =   "\\n    XTREME-S is a benchmark to evaluate universal cross-lingual speech representations in many languages.\n    XTREME-S covers four task families: speech recognition, classification, speech-to-text translation and retrieval.\n"
  
  lowerCAmelCase_   =   "\nCompute XTREME-S evaluation metric associated to each XTREME-S dataset.\nArgs:\n    predictions: list of predictions to score.\n        Each translation should be tokenized into a list of tokens.\n    references: list of lists of references for each translation.\n        Each reference should be tokenized into a list of tokens.\n    bleu_kwargs: optional dict of keywords to be passed when computing 'bleu'.\n        Keywords include Dict can be one of 'smooth_method', 'smooth_value', 'force', 'lowercase',\n        'tokenize', 'use_effective_order'.\n    wer_kwargs: optional dict of keywords to be passed when computing 'wer' and 'cer'.\n        Keywords include 'concatenate_texts'.\nReturns: depending on the XTREME-S task, one or several of:\n    \"accuracy\": Accuracy - for 'fleurs-lang_id', 'minds14'\n    \"f1\": F1 score - for 'minds14'\n    \"wer\": Word error rate - for 'mls', 'fleurs-asr', 'voxpopuli', 'babel'\n    \"cer\": Character error rate - for 'mls', 'fleurs-asr', 'voxpopuli', 'babel'\n    \"bleu\": BLEU score according to the `sacrebleu` metric - for 'covost2'\nExamples:\n\n    >>> xtreme_s_metric = datasets.load_metric('xtreme_s', 'mls')  # 'mls', 'voxpopuli', 'fleurs-asr' or 'babel'\n    >>> references = [\"it is sunny here\", \"paper and pen are essentials\"]\n    >>> predictions = [\"it's sunny\", \"paper pen are essential\"]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {'wer': 0.56, 'cer': 0.27}\n\n    >>> xtreme_s_metric = datasets.load_metric('xtreme_s', 'covost2')\n    >>> references = [\"bonjour paris\", \"il est necessaire de faire du sport de temps en temp\"]\n    >>> predictions = [\"bonjour paris\", \"il est important de faire du sport souvent\"]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {'bleu': 31.65}\n\n    >>> xtreme_s_metric = datasets.load_metric('xtreme_s', 'fleurs-lang_id')\n    >>> references = [0, 1, 0, 0, 1]\n    >>> predictions = [0, 1, 1, 0, 0]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {'accuracy': 0.6}\n\n    >>> xtreme_s_metric = datasets.load_metric('xtreme_s', 'minds14')\n    >>> references = [0, 1, 0, 0, 1]\n    >>> predictions = [0, 1, 1, 0, 0]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {'f1': 0.58, 'accuracy': 0.6}\n"
  
  lowerCAmelCase_   =   ["fleurs-asr", "mls", "voxpopuli", "babel", "covost2", "fleurs-lang_id", "minds14"]
  lowerCAmelCase_   =   ""
  
  try:
     from jiwer import transforms as tr
  
     lowerCAmelCase_   =   True
  except ImportError:
     lowerCAmelCase_   =   False
  
  if _jiwer_available and version.parse(importlib_metadata.version("jiwer")) < version.parse("2.3.0"):
  
     class 				A    (tr.AbstractTransform				):
  
  
  
           def __init__(					self     ,  lowercase_ = " "					)      ->   Union[str, Any]:
  
  
  
                  '''simple docstring'''
  
                  _snake_case      :							Tuple     				=						sentence_delimiter
  
  
  
           def    __a (					self     ,  lowercase_					)      ->   Tuple:
  
  
  
                  '''simple docstring'''
  
                  return list(lowercase_					)
  
  
  
           def    __a (					self     ,  lowercase_					)      ->   Any:
  
  
  
                  '''simple docstring'''
  
                  _snake_case      :							List[Any]     				=						[]
                  for sent_idx, sentence in enumerate(lowercase_					):
                         chars.extend(self.process_string(lowercase_					)					)
                         if self.sentence_delimiter is not None and self.sentence_delimiter != "" and sent_idx < len(lowercase_					) - 1:
                                chars.append(self.sentence_delimiter					)
                  return chars
  
  
     lowerCAmelCase_   =   tr.Compose(
         [tr.RemoveMultipleSpaces(), tr.Strip(), SentencesToListOfCharacters(SENTENCE_DELIMITER)]
     )
  elif _jiwer_available:
     lowerCAmelCase_   =   tr.Compose(
         [
             tr.RemoveMultipleSpaces(),
             tr.Strip(),
             tr.ReduceToSingleSentence(SENTENCE_DELIMITER),
             tr.ReduceToListOfListOfChars(),
         ]
     )
  else:
     lowerCAmelCase_   =   None
  
  
  
  
  def 						A_			(  lowercase_      ,		lowercase_  )			->						int:
         return float((preds == labels).mean()  )
  
  
  
  
  def 						A_			(  lowercase_      ,		lowercase_  )			->						Optional[Any]:
         return {
             "f1": float(fa_score(y_true=lowercase_      ,		y_pred=lowercase_      ,		average='''macro'''  )  ),
             "accuracy": simple_accuracy(lowercase_      ,		lowercase_  ),
         }
  
  
  
  
  def 						A_			(  lowercase_      ,		lowercase_      ,		lowercase_="exp"      ,		lowercase_=None      ,		lowercase_=False      ,		lowercase_=False      ,		lowercase_=None      ,		lowercase_=False      ,		)			->						Any:
         # xtreme-s can only have one label
         _snake_case      :							Optional[Any]     				=						[[label] for label in labels]
         _snake_case      :							List[Any]     				=						list(lowercase_  )
         try:
                import sacrebleu as scb
         except ImportError:
                raise ValueError(
                    '''sacrebleu has to be installed in order to apply the bleu metric for covost2.'''
                    '''You can install it via `pip install sacrebleu`.'''  )
  
         if version.parse(scb.__version__  ) < version.parse('''1.4.12'''  ):
                raise ImportWarning(
                    '''To use `sacrebleu`, the module `sacrebleu>=1.4.12` is required, and the current version of `sacrebleu` doesn\'t match this condition.\n'''
                    '''You can install it with `pip install "sacrebleu>=1.4.12"`.'''  )
  
         _snake_case      :							Optional[int]     				=						len(labels[0]  )
         if any(len(lowercase_  ) != references_per_prediction for refs in labels  ):
                raise ValueError('''Sacrebleu requires the same number of references for each prediction'''  )
         _snake_case      :							List[str]     				=						[[refs[i] for refs in labels] for i in range(lowercase_  )]
         _snake_case      :							int     				=						scb.corpus_bleu(
             lowercase_      ,		lowercase_      ,		smooth_method=lowercase_      ,		smooth_value=lowercase_      ,		force=lowercase_      ,		lowercase=lowercase_      ,		use_effective_order=lowercase_      ,		**({'''tokenize''': tokenize} if tokenize else {})      ,		)
         return {"bleu": output.score}
  
  
  
  
  def 						A_			(  lowercase_      ,		lowercase_      ,		lowercase_      ,		lowercase_  )			->						str:
         try:
                from jiwer import compute_measures
         except ImportError:
                raise ValueError(
                    f'''jiwer has to be installed in order to apply the wer metric for {config_name}.'''
                    '''You can install it via `pip install jiwer`.'''  )
  
         if concatenate_texts:
                _snake_case      :							Any     				=						compute_measures(lowercase_      ,		lowercase_  )['''wer''']
  
                _snake_case      :							Tuple     				=						compute_measures(lowercase_      ,		lowercase_      ,		truth_transform=lowercase_      ,		hypothesis_transform=lowercase_  )['''wer''']
                return {"wer": wer, "cer": cer}
         else:
  
                def compute_score(lowercase_      ,		lowercase_      ,		lowercase_="wer"  ):
                       _snake_case      :							List[Any]     				=						0
                       _snake_case      :							Union[str, Any]     				=						0
                       for prediction, reference in zip(lowercase_      ,		lowercase_  ):
                              if score_type == "wer":
                                     _snake_case      :							Optional[int]     				=						compute_measures(lowercase_      ,		lowercase_  )
                              elif score_type == "cer":
                                     _snake_case      :							Any     				=						compute_measures(
                                         lowercase_      ,		lowercase_      ,		truth_transform=lowercase_      ,		hypothesis_transform=lowercase_  )
                              incorrect += measures["substitutions"] + measures["deletions"] + measures["insertions"]
                              total += measures["substitutions"] + measures["deletions"] + measures["hits"]
                       return incorrect / total
  
                return {"wer": compute_score(lowercase_      ,		lowercase_      ,		'''wer'''  ), "cer": compute_score(lowercase_      ,		lowercase_      ,		'''cer'''  )}
  
  @datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION       ,_KWARGS_DESCRIPTION				)
  class 				A    (datasets.Metric				):
  
  
  
        def    __a (					self					)      ->   Tuple:
  
  
  
               '''simple docstring'''
  
               if self.config_name not in _CONFIG_NAMES:
                      raise KeyError(F'''You should supply a configuration name selected in {_CONFIG_NAMES}'''					)
  
               _snake_case      :							int     				=						'''int64''' if self.config_name in ['''fleurs-lang_id''', '''minds14'''] else '''string'''
  
               return datasets.MetricInfo(
                   description=_DESCRIPTION     ,  citation=_CITATION     ,  inputs_description=_KWARGS_DESCRIPTION     ,  features=datasets.Features(
                       {'''predictions''': datasets.Value(lowercase_					), '''references''': datasets.Value(lowercase_					)}					)     ,  codebase_urls=[]     ,  reference_urls=[]     ,  format='''numpy'''     ,  )
  
  
  
        def    __a (					self     ,  lowercase_     ,  lowercase_     ,  lowercase_=None     ,  lowercase_=None					)      ->   Optional[Any]:
  
  
  
               '''simple docstring'''
  
               _snake_case      :							List[str]     				=						bleu_kwargs if bleu_kwargs is not None else {}
               _snake_case      :							str     				=						wer_kwargs if wer_kwargs is not None else {}
  
               if self.config_name == "fleurs-lang_id":
                      return {"accuracy": simple_accuracy(lowercase_     ,  lowercase_					)}
               elif self.config_name == "minds14":
                      return fa_and_simple_accuracy(lowercase_     ,  lowercase_					)
               elif self.config_name == "covost2":
                      _snake_case      :							Tuple     				=						bleu_kwargs.pop('''smooth_method'''     ,  '''exp'''					)
                      _snake_case      :							List[Any]     				=						bleu_kwargs.pop('''smooth_value'''     ,  lowercase_					)
                      _snake_case      :							int     				=						bleu_kwargs.pop('''force'''     ,  lowercase_					)
                      _snake_case      :							List[Any]     				=						bleu_kwargs.pop('''lowercase'''     ,  lowercase_					)
                      _snake_case      :							List[str]     				=						bleu_kwargs.pop('''tokenize'''     ,  lowercase_					)
                      _snake_case      :							Tuple     				=						bleu_kwargs.pop('''use_effective_order'''     ,  lowercase_					)
                      return bleu(
                          preds=lowercase_     ,  labels=lowercase_     ,  smooth_method=lowercase_     ,  smooth_value=lowercase_     ,  force=lowercase_     ,  lowercase=lowercase_     ,  tokenize=lowercase_     ,  use_effective_order=lowercase_     ,  )
               elif self.config_name in ["fleurs-asr", "mls", "voxpopuli", "babel"]:
                      _snake_case      :							Any     				=						wer_kwargs.pop('''concatenate_texts'''     ,  lowercase_					)
                      return wer_and_cer(lowercase_     ,  lowercase_     ,  lowercase_     ,  self.config_name					)
               else:
                      raise KeyError(F'''You should supply a configuration name selected in {_CONFIG_NAMES}'''					)
  
  
  
  
  
  
  
style_context: 
  
  
  
  
  
  from __future__ import annotations
  
  class 				A    :
  
  
  
        def __init__(					self     ,  lowercase_					)      ->   None:
  
  
  
               '''simple docstring'''
  
               _snake_case      :							Optional[Any]     				=						vertices
               _snake_case      :							int     				=						[[0] * vertices for _ in range(lowercase_					)]
  
  
  
        def    __a (					self     ,  lowercase_					)      ->   None:
  
  
  
               '''simple docstring'''
  
               print('''Vertex \t Distance from Source'''					)
               for vertex in range(self.vertices					):
                      print(lowercase_     ,  '''\t\t'''     ,  distances_from_source[vertex]					)
  
  
  
        def    __a (					self     ,  lowercase_     ,  lowercase_					)      ->   int:
  
  
  
               '''simple docstring'''
  
               _snake_case      :							List[Any]     				=						1E7
               _snake_case      :							Tuple     				=						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:
                             _snake_case      :							Dict     				=						distances_from_source[vertex]
                             _snake_case      :							int     				=						vertex
               return min_index
  
  
  
        def    __a (					self     ,  lowercase_					)      ->   None:
  
  
  
               '''simple docstring'''
  
               _snake_case      :							List[Any]     				=						[int(1E7					)] * self.vertices  # distances from the source
               _snake_case      :							List[Any]     				=						0
               _snake_case      :							List[str]     				=						[False] * self.vertices
  
               for _ in range(self.vertices					):
                      _snake_case      :							List[Any]     				=						self.minimum_distance(lowercase_     ,  lowercase_					)
                      _snake_case      :							List[str]     				=						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]
                             ):
                                    _snake_case      :							Any     				=						distances[u] + self.graph[u][v]
  
               self.print_solution(lowercase_					)
  
  
  if __name__ == "__main__":
     lowerCAmelCase_   =   Graph(9)
     lowerCAmelCase_   =   [
         [0, 4, 0, 0, 0, 0, 0, 8, 0],
         [4, 0, 8, 0, 0, 0, 0, 1_1, 0],
         [0, 8, 0, 7, 0, 4, 0, 0, 2],
         [0, 0, 7, 0, 9, 1_4, 0, 0, 0],
         [0, 0, 0, 9, 0, 1_0, 0, 0, 0],
         [0, 0, 4, 1_4, 1_0, 0, 2, 0, 0],
         [0, 0, 0, 0, 0, 2, 0, 1, 6],
         [8, 1_1, 0, 0, 0, 0, 1, 0, 7],
         [0, 0, 2, 0, 0, 0, 6, 7, 0],
     ]
     graph.dijkstra(0)
  
  
  
  
  
  
  