




from __future__ import annotations
class       _UpperCamelCase   :
      def __init__(      self :Union[str, Any]			,   lowerCamelCase :str   )  ->      Any:
       UpperCAmelCase__							=    vertices
       UpperCAmelCase__							=    [[0] * vertices for _ in range(UpperCamelCase__   )]
      def 						UpperCAmelCase_    (      self :str			,   lowerCamelCase :List[str]   )  ->      Optional[Any]:
       print("Vertex \t Distance from Source"   )
       for vertex in range(self.vertices   ):
        print(UpperCamelCase__			,   "\t\t"			,   distances_from_source[vertex]   )
      def 						UpperCAmelCase_    (      self :Optional[Any]			,   lowerCamelCase :Dict			,   lowerCamelCase :Union[str, Any]   )  ->      int:
       UpperCAmelCase__							=    1e7
       UpperCAmelCase__							=    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:
         UpperCAmelCase__							=    distances_from_source[vertex]
         UpperCAmelCase__							=    vertex
       return min_index







      def 						UpperCAmelCase_    (      self :Optional[int]			,   lowerCamelCase :Any   )  ->      List[str]:
       UpperCAmelCase__							=    [int(1e7   )] * self.vertices  # distances from the source
       UpperCAmelCase__							=    0
       UpperCAmelCase__							=    [False] * self.vertices

       for _ in range(self.vertices   ):
        UpperCAmelCase__							=    self.minimum_distance(UpperCamelCase__			,   UpperCamelCase__   )
        UpperCAmelCase__							=    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]
         ):
          UpperCAmelCase__							=    distances[u] + self.graph[u][v]

       self.print_solution(UpperCamelCase__   )


if __name__ == "__main__":
  _lowerCAmelCase    : List[Any]		= Graph(9)
  _lowerCAmelCase    : str		= [
      [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)













import json
import os
import unittest

from transformers import HerbertTokenizer, HerbertTokenizerFast
from transformers.models.herbert.tokenization_herbert import VOCAB_FILES_NAMES
from transformers.testing_utils import get_tests_dir, require_tokenizers, slow

from ...test_tokenization_common import TokenizerTesterMixin


@require_tokenizers
class 				__a				(	__A			,						unittest.TestCase    ):





		'''simple docstring'''



		UpperCAmelCase__   :					Optional[Any]					     =    HerbertTokenizer
		UpperCAmelCase__   :					List[Any]					     =    HerbertTokenizerFast
		UpperCAmelCase__   :					Optional[Any]					     =    True


		def 	__snake_case      (    self							):
						super().setUp()

						# Use a simpler test file without japanese/chinese characters
						with open(F'''{get_tests_dir()}/fixtures/sample_text_no_unicode.txt'''			,     encoding='utf-8'							) as f_data:
										SCREAMING_SNAKE_CASE_ :						Dict    				= f_data.read().replace('\n\n'			,     '\n'							).strip()

						SCREAMING_SNAKE_CASE_ :						str    				= [
						    '<s>',
						    '</s>',
						    'l',
						    'o',
						    'w',
						    'e',
						    'r',
						    's',
						    't',
						    'i',
						    'd',
						    'n',
						    'w</w>',
						    'r</w>',
						    't</w>',
						    'lo',
						    'low',
						    'er</w>',
						    'low</w>',
						    'lowest</w>',
						    'newer</w>',
						    'wider</w>',
						    ',</w>',
						    '<unk>',
						]
						SCREAMING_SNAKE_CASE_ :						str    				= dict(zip(UpperCamelCase__			,     range(len(UpperCamelCase__							)							)							)							)
						SCREAMING_SNAKE_CASE_ :						Optional[int]    				= ['l o 123', 'lo w 1456', 'e r</w> 1789', '']

						SCREAMING_SNAKE_CASE_ :						int    				= os.path.join(self.tmpdirname			,     VOCAB_FILES_NAMES['vocab_file']							)
						SCREAMING_SNAKE_CASE_ :						int    				= os.path.join(self.tmpdirname			,     VOCAB_FILES_NAMES['merges_file']							)
						with open(self.vocab_file			,     'w'							) as fp:
										fp.write(json.dumps(UpperCamelCase__							)							)
						with open(self.merges_file			,     'w'							) as fp:
										fp.write('\n'.join(UpperCamelCase__							)							)


		def 	__snake_case      (    self			,     UpperCamelCase__							):
						SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= 'lower newer'
						SCREAMING_SNAKE_CASE_ :						int    				= 'lower newer'
						return input_text, output_text


		def 	__snake_case      (    self							):
						SCREAMING_SNAKE_CASE_ :						List[Any]    				= self.tokenizer_class(vocab_file=self.vocab_file			,     merges_file=self.merges_file							)

						SCREAMING_SNAKE_CASE_ :						Optional[int]    				= 'lower'
						SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= ['low', 'er</w>']
						SCREAMING_SNAKE_CASE_ :						int    				= tokenizer.tokenize(UpperCamelCase__							)
						self.assertListEqual(UpperCamelCase__			,     UpperCamelCase__							)

						SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= tokens + ['<unk>']
						SCREAMING_SNAKE_CASE_ :						List[Any]    				= [16, 17, 23]
						self.assertListEqual(tokenizer.convert_tokens_to_ids(UpperCamelCase__							)			,     UpperCamelCase__							)


		def 	__snake_case      (    self							):
						if not self.test_rust_tokenizer:
										return

						SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= self.get_tokenizer()
						SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= self.get_rust_tokenizer()

						SCREAMING_SNAKE_CASE_ :						List[str]    				= 'lower,newer'

						SCREAMING_SNAKE_CASE_ :						Optional[int]    				= tokenizer.tokenize(UpperCamelCase__							)
						SCREAMING_SNAKE_CASE_ :						Tuple    				= rust_tokenizer.tokenize(UpperCamelCase__							)
						self.assertListEqual(UpperCamelCase__			,     UpperCamelCase__							)

						SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= tokenizer.encode(UpperCamelCase__			,     add_special_tokens=UpperCamelCase__							)
						SCREAMING_SNAKE_CASE_ :						Any    				= rust_tokenizer.encode(UpperCamelCase__			,     add_special_tokens=UpperCamelCase__							)
						self.assertListEqual(UpperCamelCase__			,     UpperCamelCase__							)

						SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= self.get_rust_tokenizer()
						SCREAMING_SNAKE_CASE_ :						Dict    				= tokenizer.encode(UpperCamelCase__							)
						SCREAMING_SNAKE_CASE_ :						Optional[int]    				= rust_tokenizer.encode(UpperCamelCase__							)
						self.assertListEqual(UpperCamelCase__			,     UpperCamelCase__							)






		@slow
		def 	__snake_case      (    self							):
						SCREAMING_SNAKE_CASE_ :						Optional[int]    				= self.tokenizer_class.from_pretrained('allegro/herbert-base-cased'							)

						SCREAMING_SNAKE_CASE_ :						List[str]    				= tokenizer.encode('konstruowanie sekwencji'			,     add_special_tokens=UpperCamelCase__							)
						SCREAMING_SNAKE_CASE_ :						Optional[int]    				= tokenizer.encode('konstruowanie wielu sekwencji'			,     add_special_tokens=UpperCamelCase__							)

						SCREAMING_SNAKE_CASE_ :						Any    				= tokenizer.build_inputs_with_special_tokens(UpperCamelCase__							)
						SCREAMING_SNAKE_CASE_ :						Dict    				= tokenizer.build_inputs_with_special_tokens(UpperCamelCase__			,     UpperCamelCase__							)

						assert encoded_sentence == [0] + text + [2]
						assert encoded_pair == [0] + text + [2] + text_a + [2]