def find_shortest_path(graph, start, end):
  """
  Знаходить найкоротший шлях між двома вершинами орієнтованого графа.
 
  Args:
    graph: Орієнтований граф.
    start: Початкова вершина.
    end: Кінцева вершина.
 
  Returns:
    Список вершин, що утворюють найкоротший шлях.
  """
 
  # Створюємо матрицю відстаней між вершинами.
  distances = [[float("inf")] * len(graph) for _ in range(len(graph))]
  distances[start][start] = 0
 
  # Виконуємо алгоритм Дейкстри.
  for vertex in range(len(graph)):
    for neighbor in graph[vertex]:
      if distances[vertex][neighbor] > distances[vertex][start] + graph[vertex][neighbor]:
        distances[neighbor] = distances[vertex][start] + graph[vertex][neighbor]
 
  # Повертаємо список вершин, що утворюють найкоротший шлях.
  path = [end]
  while path[-1] != start:
    for neighbor in graph[path[-1]]:
      if distances[path[-1]][neighbor] == distances[end] - graph[path[-1]][neighbor]:
        path.append(neighbor)
        break
  return path[::-1]
 
 
if __name__ == "__main__":
  # Створюємо граф.
  graph = [[0, 10, 5], [10, 0, 2], [5, 2, 0]]
 
  # Знаходимо найкоротший шлях.
  path = find_shortest_path(graph, 0, 2)
 
  # Виводимо результат.
  print("Найкоротший шлях:", path)
 

ZGVmIGZpbmRfc2hvcnRlc3RfcGF0aChncmFwaCwgc3RhcnQsIGVuZCk6CiAgIiIiCiAg0JfQvdCw0YXQvtC00LjRgtGMINC90LDQudC60L7RgNC+0YLRiNC40Lkg0YjQu9GP0YUg0LzRltC2INC00LLQvtC80LAg0LLQtdGA0YjQuNC90LDQvNC4INC+0YDRltGU0L3RgtC+0LLQsNC90L7Qs9C+INCz0YDQsNGE0LAuCgogIEFyZ3M6CiAgICBncmFwaDog0J7RgNGW0ZTQvdGC0L7QstCw0L3QuNC5INCz0YDQsNGELgogICAgc3RhcnQ6INCf0L7Rh9Cw0YLQutC+0LLQsCDQstC10YDRiNC40L3QsC4KICAgIGVuZDog0JrRltC90YbQtdCy0LAg0LLQtdGA0YjQuNC90LAuCgogIFJldHVybnM6CiAgICDQodC/0LjRgdC+0Log0LLQtdGA0YjQuNC9LCDRidC+INGD0YLQstC+0YDRjtGO0YLRjCDQvdCw0LnQutC+0YDQvtGC0YjQuNC5INGI0LvRj9GFLgogICIiIgoKICAjINCh0YLQstC+0YDRjtGU0LzQviDQvNCw0YLRgNC40YbRjiDQstGW0LTRgdGC0LDQvdC10Lkg0LzRltC2INCy0LXRgNGI0LjQvdCw0LzQuC4KICBkaXN0YW5jZXMgPSBbW2Zsb2F0KCJpbmYiKV0gKiBsZW4oZ3JhcGgpIGZvciBfIGluIHJhbmdlKGxlbihncmFwaCkpXQogIGRpc3RhbmNlc1tzdGFydF1bc3RhcnRdID0gMAoKICAjINCS0LjQutC+0L3Rg9GU0LzQviDQsNC70LPQvtGA0LjRgtC8INCU0LXQudC60YHRgtGA0LguCiAgZm9yIHZlcnRleCBpbiByYW5nZShsZW4oZ3JhcGgpKToKICAgIGZvciBuZWlnaGJvciBpbiBncmFwaFt2ZXJ0ZXhdOgogICAgICBpZiBkaXN0YW5jZXNbdmVydGV4XVtuZWlnaGJvcl0gPiBkaXN0YW5jZXNbdmVydGV4XVtzdGFydF0gKyBncmFwaFt2ZXJ0ZXhdW25laWdoYm9yXToKICAgICAgICBkaXN0YW5jZXNbbmVpZ2hib3JdID0gZGlzdGFuY2VzW3ZlcnRleF1bc3RhcnRdICsgZ3JhcGhbdmVydGV4XVtuZWlnaGJvcl0KCiAgIyDQn9C+0LLQtdGA0YLQsNGU0LzQviDRgdC/0LjRgdC+0Log0LLQtdGA0YjQuNC9LCDRidC+INGD0YLQstC+0YDRjtGO0YLRjCDQvdCw0LnQutC+0YDQvtGC0YjQuNC5INGI0LvRj9GFLgogIHBhdGggPSBbZW5kXQogIHdoaWxlIHBhdGhbLTFdICE9IHN0YXJ0OgogICAgZm9yIG5laWdoYm9yIGluIGdyYXBoW3BhdGhbLTFdXToKICAgICAgaWYgZGlzdGFuY2VzW3BhdGhbLTFdXVtuZWlnaGJvcl0gPT0gZGlzdGFuY2VzW2VuZF0gLSBncmFwaFtwYXRoWy0xXV1bbmVpZ2hib3JdOgogICAgICAgIHBhdGguYXBwZW5kKG5laWdoYm9yKQogICAgICAgIGJyZWFrCiAgcmV0dXJuIHBhdGhbOjotMV0KCgppZiBfX25hbWVfXyA9PSAiX19tYWluX18iOgogICMg0KHRgtCy0L7RgNGO0ZTQvNC+INCz0YDQsNGELgogIGdyYXBoID0gW1swLCAxMCwgNV0sIFsxMCwgMCwgMl0sIFs1LCAyLCAwXV0KCiAgIyDQl9C90LDRhdC+0LTQuNC80L4g0L3QsNC50LrQvtGA0L7RgtGI0LjQuSDRiNC70Y/RhS4KICBwYXRoID0gZmluZF9zaG9ydGVzdF9wYXRoKGdyYXBoLCAwLCAyKQoKICAjINCS0LjQstC+0LTQuNC80L4g0YDQtdC30YPQu9GM0YLQsNGCLgogIHByaW50KCLQndCw0LnQutC+0YDQvtGC0YjQuNC5INGI0LvRj9GFOiIsIHBhdGgpCg==