Theory and Tasks for Students - Spring 2019
Графы

E1 Заправки

Формализовать и решить следующую задачу:
В стране N городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге, требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-ый, потратив как можно меньшее количество денег.

Формат входных данных

В первой строке вводится число N (1 <= N <= 1000), в следующей идет N чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 1000). Затем идет число M – количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами – номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя.

Формат выходных данных

Одно число – суммарную стоимость маршрута или -1, если добраться невозможно.

Примеры

Входные данные: 5 3 6 1 7 6 8 1 2 5 4 5 1 3 4 5 2 2 4 2 3 3 1

Выходные данные: 3

E2 AVL

Визуализировать AVL-дерево и реализовать операции с ним:

  • Добавление пары "ключ-значение";
  • Поиск вершины по ключу;
  • Удаление вершины по ключу;
  • Вывод пар "ключ-значение" в порядке возрастания ключей (центрированный обход LNR);
  • Вывод пар "ключ-значение" в порядке прямого обхода NLR;
  • Вывод пар "ключ-значение" в порядке обратного обхода LRN.

При изменении добавлении и удалении элементов должна производиться перебалансировка.