Yarodash

Dijkstra algo

Apr 15th, 2021
786
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import copy
  2.  
  3.  
  4. class InvalidHeapSize(Exception):
  5.     def __init__(self):
  6.         pass
  7.  
  8.     def __repr__(self):
  9.         return 'Tried to create heap non-positive size'
  10.  
  11.  
  12. class InvalidHeapPosition(Exception):
  13.     def __init__(self, pos, size):
  14.         self.pos, self.size = pos, size
  15.  
  16.     def __repr__(self):
  17.         return f'Invalid position ({self.pos}), position must be in [0; {self.size})'
  18.  
  19.  
  20. class EmptyHeapException(Exception):
  21.     def __init__(self):
  22.         pass
  23.  
  24.     def __repr__(self):
  25.         return 'You can not use remove_top, heap size is 0'
  26.  
  27.  
  28. class Heap:
  29.     __inf__ = 10**18+1
  30.  
  31.     def __init__(self, initial_length: int):
  32.         if initial_length <= 0:
  33.             raise InvalidHeapSize
  34.  
  35.         self.initial_length = initial_length
  36.         self.size = 1
  37.         while self.size < initial_length:
  38.             self.size *= 2
  39.         self.shift = self.size-1
  40.         self.data_size = self.size
  41.         self.size = 2*self.size-1
  42.  
  43.         self.items = [[self.__inf__, None] for i in range(self.size)]
  44.  
  45.     @staticmethod
  46.     def parent(pos):
  47.         return (pos-1)//2
  48.  
  49.     @staticmethod
  50.     def left_child(pos):
  51.         return pos*2+1
  52.  
  53.     @staticmethod
  54.     def right_child(pos):
  55.         return pos*2+2
  56.  
  57.     def set(self, position: int, value: int):
  58.         if position < 0 or position > self.initial_length:
  59.             raise InvalidHeapPosition(position, self.initial_length)
  60.  
  61.         self.items[self.shift+position] = [value, position]
  62.         self.go_top(self.shift+position)
  63.  
  64.     def go_top(self, position):
  65.         while position > 0:
  66.             parent = self.parent(position)
  67.             if self.items[position][0] < self.items[parent][0]:
  68.                 self.items[parent] = copy.copy(self.items[position])
  69.                 position = parent
  70.             else:
  71.                 break
  72.  
  73.     def update_from_bottom(self, position):
  74.         while position > 0:
  75.             position = self.parent(position)
  76.             left, right = self.left_child(position), self.right_child(position)
  77.             smaller = left if self.items[left][0] < self.items[right][0] else right
  78.             self.items[position] = copy.copy(self.items[smaller])
  79.  
  80.     def remove_top(self):
  81.         if self.items[0][1] is None:
  82.             raise EmptyHeapException
  83.  
  84.         position = self.items[0][1]
  85.         self.items[self.shift+position] = [self.__inf__, None]
  86.         self.update_from_bottom(self.shift+position)
  87.  
  88.     def get(self):
  89.         return self.items[0][1]
  90.  
  91.     def __repr__(self):
  92.         return 'Heap:\n'+'\n'.join(f'{key}: {value}' for key, value in self.items)
  93.  
  94.  
  95. def main():
  96.     n, start, finish = list(map(int, input().split()))
  97.     start -= 1
  98.     finish -= 1
  99.  
  100.     edges = [[] for i in range(n)]
  101.  
  102.     for i in range(n):
  103.         data = list(map(int, input().split()))
  104.         for index, edge in zip(range(n), data):
  105.             if edge > 0:
  106.                 edges[i].append((index, edge))
  107.  
  108.     heap = Heap(n)
  109.  
  110.     w = [10**18]*n
  111.     w[start] = 0
  112.     for i in range(n):
  113.         heap.set(i, 10**18)
  114.     heap.set(start, 0)
  115.  
  116.     for k in range(n):
  117.         ver = heap.get()
  118.  
  119.         for index, edge in edges[ver]:
  120.             if w[index] > w[ver]+edge:
  121.                 w[index] = w[ver]+edge
  122.                 heap.set(index, w[ver]+edge)
  123.         heap.remove_top()
  124.  
  125.     if w[finish] >= 10**18:
  126.         print(-1)
  127.     else:
  128.         print(w[finish])
  129.  
  130.  
  131. if __name__ == '__main__':
  132.     main()
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×