В данной задаче необходимо найти путь передачи сообщения от Поликарпа, проживающего в Ханты-Мансийске, де Кодеру, проживающему в Париже.

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

Таким образом, при передаче могут быть необходимы только люди, живущие в Дубае, Москве и Калининграде, и всегда происходит ровно четыре передачи.

В дальнейшем подсчет стоимостей одной передачи сообщения происходит самым простым способом — одним циклом находя наибольший общий префикс. Как \(n\) обозначается суммарное количество людей во всех городах.

Можно перебрать, через каких людей в промежуточных городах передается сообщение, и найти минимальную стоимость. Это решение работает за \(O(n^3)\) и получает 40 баллов.

Задачу можно сформулировать как задачу нахождения кратчайшего пути в графе, в котором вершинами являются люди, а рёбра соответствуют передаче сообщения напрямую и стоят соответствующее число кредитов. Построение графа занимает \(O(n^2)\) времени. Искать кратчайший путь в графе можно несколькими алгоритмами:

1. Алгоритм Флойда за \(O(n^3)\) получает 40 баллов.
2. Алгоритм Дейкстры за \(O(n^2)\) получает 60 баллов.
3. Можно заметить, что граф ациклический и искать кратчайший путь в нем стандартным алгоритмом за \(O(n^2)\) и получить 60 баллов.

Последний способ поиска кратчайшего пути наталкивает на идею решения данной задачи с использованием динамического программирования (ДП). Для каждого человека считается минимальная стоимость передачи ему сообщения. Так как выгодно передавать сообщение только в следующий часовой пояс (из Ханты-Мансийска в Дубай, из Дубая в Москву и так далее), то эту стоимость можно считать в порядке этих часовых поясов. Для некоторого человека из текущего часового пояса можно перебрать, кто из предыдущего часового пояса передаст ему сообщение, и из всех таких способов выбрать самый дешёвый. Это решение работает за \(O(n^2)\) и получает 60 баллов.

Можно попытаться использовать это решение и при бо́льших \(n\): для того, чтобы уложиться во временной лимит, можно в каждом городе при переходе к следующему сохранять только некоторое количество лучших (кому дешевле всего передать сообщение). Если оставлять 3000 человек, то такое решение получает 70 баллов.

Полные решения (100 баллов)

Используя аналогичную идею ДП, считать значения быстрее:

1. Предварительно отсортировать номера в каждом часовом поясе. Считая значение ДП для некоторого человека, перебирать длину совпадающего префикса его номера, находить (с помощью двоичного поиска) отрезок людей в предыдущем часовом поясе с таким префиксом номера. На этом отрезке находить минимальное значение ДП с использованием, например, дерева отрезков.
   Это решение работает за \(O(n\log n)\).
2. Аналогично необходимо предварительно отсортировать номера в каждом часовом поясе (это можно сделать за \(O(n)\) с использованием цифровой сортировки). Используя идею «двух указателей», последовательно считать значения ДП для людей из текущего часового пояса, двигая второй указатель в предыдущем часовом поясе, пока номер человека в предыдущем часовом поясе лексикографически меньше номера человека из текущего часового пояса (для которого считается значение ДП). Для каждой длины совпадающего префикса номера текущего человека хранится минимальная стоимость передачи сообщения человеку из предыдущего часового пояса, имеющего номер с совпадающим префиксом. При перемещении указателя в предыдущем часовом поясе эти значения несложно пересчитываются. После прохода «двумя указателями» в одну сторону необходимо пройти указателями в другую сторону и выбрать из полученных способов минимальный по стоимости.
   Это решение работает за \(O(n)\).
3. Используя идею meet-in-the-middle («встреча посередине»), можно для каждого человека, проживающего в Москве, посчитать минимальную стоимость передачи сообщения ему из Ханты-Мансийска через человека в Дубае и в Париж через человека в Калининграде. Необходимо заметить, что передавать сообщение человеку А, проживающему в Москве, надо через человека, проживающего в Дубае и имеющего наибольший совпадающий префикс или с Поликарпом, или с А.
   Таким образом, такой подсчёт можно реализовать методом «двух указателей» за \(O(n)\).