Автор задачи: Александр Гордеев, разработчик: Егор Юлин
Будем воспринимать небоскребы как вершины графа, а возможные перемещения между ними — как ребра. В задаче интуитивно хочется построить граф на $$$n$$$ вершинах, между которыми есть ребра двух типов: ребра из первого мира и из второго. Но тогда становится сложно учитывать, что для смены типа ребра нам также нужно потратить $$$x$$$ секунд для перемещения между мирами.
Стандартный подход в задачах такого рода — завести больше вершин в графе. Каждая вершина нового графа будет отвечать за пару $$$(v, \mathtt{state})$$$, где $$$v$$$ — вершина исходного графа, а $$$\mathtt{state}$$$ — «состояние» путешествующего по графу. В данном случае состояние будет задавать то, в каком мире Майлз находится, поэтому нам понадобится $$$2n$$$ вершин: $$$n$$$ соответствующих небоскребам первого мира, $$$n$$$ — второго. Далее в качестве индекса у вершины будем указывать номер мира, которому она соответствует.
Теперь осталось построить ребра в таком графе. Для этого просто проведем по ребру между любыми двумя небоскребами, между которыми возможно перемещение:
Теперь любому пути, удовлетворяющему условию, соответствует путь в нашем графе, и наоборот. Поэтому нам остается только найти кратчайший путь из вершины $$$s_1$$$ (небоскреб $$$s$$$ в первом мире) в вершину $$$t_2$$$ (небоскреб $$$t$$$ во втором мире). Поскольку все веса в графе неотрицательны, для этого можно воспользоваться алгоритмом Дейкстры, и получить решение за время $$$\mathcal{O}((m_1 + m_2 + n) \log n)$$$.