# 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