eternals

ACM и кружок в институте дали следующее:
1. Во-первых, заставил рассматривать разные данные на входе. Т.к. тесты на большинство особых данных были и задачи тупо не засчитывались. После этого стало уже не возможным, например, пропустить деление на ноль.
2. Лично для меня вступление в этот кружок дало некоторое отрезвление, т.к. я стал вращаться среди людей, которые многое в ИТ умели лучше меня. До этого что в школе, что в лицее, что в самой группе в институте не имел возможности ни с кем конкурировать, т.к. был на много голов выше.
3. Решение задач в фиксированные сроки. Оценка и расстановка приоритетов — какие задачи в каком порядке кому решать.
4. Типовые задачи мы оттачивали на занятиях в кружке. Это тоже дало некоторую базу для дальнейшего движения.
5. Оптимизационные алгоритмы — это особая ценность. Их было много, они были и весьма не простые. Нужно было ещё ориентироваться, когда что применять. Очень помогает сейчас.

Если типовые инструменты нельзя использовать, то постройте простейшее бинарное дерево. Лочить при перестроении отдельные ноды.

Перебором, конечно. И как написали выше, с применением «динамического программирования», т.е. запоминать и использовать уже рассчитанные варианты и подварианты.

В реальной жизни такие задачи стараются решать зональным способом. А для Москвы и, наверное, Питера в виде секторов вокруг веток метро. Чтобы в секторе было удобно перемещаться. Сектора могут немного накладываться друг на друга. Затем для леммингов подбираете маршрут исходя из предпочтения находиться в одном секторе или максимум смежных. Ну и количество точек учитываете. Можно далее учесть и их отдалённость и последовательность обхода задать.

Просто решать перебором на полной карте — это строить ветки метро, наземного транспорта, учитывать водные преграды, сраные железнодорожные пути, пробки, стоимость проезда сложнее высчитать. В итоге вы одного курьера на 50% будете использовать, а другого на 150%.