Автор задачи и разработчик: Даниил Орешников
Это вариация классической задаче о дереве Штейнера — минимальном остовном дереве графа, соединяющем множество заранее заданных вершин. Для произвольного числа выбранных вершин эта задача является NP-трудной, однако данная задача сводится к задаче о дереве Штейнера для трех вершин.
Нам требуется выбрать некоторое множество вершин, чтобы по ним можно было добраться от любого из трех изначально заданных связных множеств вершин до другого. Обозначим изначальные множества за $$$A_1$$$, $$$A_2$$$ и $$$A_3$$$, а искомое множество связывающих их вершин — за $$$B$$$. Тогда заметим, что каждая из вершин $$$B$$$ лежит на каком-то пути между $$$A_i$$$ и $$$A_j$$$ для $$$i \neq j$$$, иначе эту вершину можно удалить, и ответ станет меньше.
Посмотрим, как множество $$$B$$$ может выглядеть.
Итого, $$$B$$$ можно получить либо как объединение двух минимальных путей между двумя парами данных множеств, либо как объединение трех кратчайших путей от некоторой вершины $$$v$$$ до каждого из множеств. Чтобы все эти кратчайшие пути вычислить, сделаем множественный bfs из каждого из $$$A_i$$$ и найдем $$$\mathtt{d}_i(v)$$$ — длину кратчайшего пути от какой-то из вершины $$$A_i$$$ до $$$v$$$.
Теперь если обозначить за $$$\mathtt{D}_i(j)$$$ величину $$$\min\limits_{v \in A_j} \mathtt{d}_i(v)$$$, ответ равен $$$$$$\min\left(\mathtt{D}_1(2) + \mathtt{D}_1(2), \mathtt{D}_2(1) + \mathtt{D}_2(3), \mathtt{D}_3(1) + \mathtt{D}_3(2), \min\limits_{v=1}^n (\mathtt{d}_1(v) + \mathtt{d}_2(v) + \mathtt{d}_3(v) + 1)\right) \text{.}$$$$$$ Только надо аккуратно учесть, что расстояния надо считать в вершинах, а не в ребрах.