Кратчайший путь. Есть 7 городов, обозначенных буквами английского алфавита A, B, C, D, E, F, G. Вы хотите посетить эти все города ровно по одному разу каждый и вернуться в начальную точку своего путешествия. Для этого вы можете воспользоваться самолётами: между двумя любыми городами есть прямой авиарейс. Стоимость перелёта между парой городов приведена в следующей таблице. Необходимо построить замкнутый маршрут, проходящий через все города по одному разу, стоимость перелёта по которому была бы минимально возможной. Расположите города в том порядке, в котором вы будете их посещать. Чем короче будет найденный вами маршрут, тем больше баллов вы получите. Обратите внимание: при расчёте стоимости маршрута также учитывается перелёт из последнего города вашего ответа в первый город.

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

1. A -> B (стоимость 2)
2. B -> C (стоимость 3)
3. C -> D (стоимость 4)
4. D -> E (стоимость 5)
5. E -> F (стоимость 6)
6. F -> G (стоимость 7)
7. G -> A (стоимость 8)

Общая стоимость маршрута будет равна 2 + 3 + 4 + 5 + 6 + 7 + 8 = 35.

Таким образом, кратчайший маршрут будет: A -> B -> C -> D -> E -> F -> G -> A.