Представим карту страны как граф, в котором вершинам будут соответствовать города, а ребрам — дороги между ними.

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

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

Если граничные города есть, удалим все ребра, ведущие в них. После этого граф должен распасться ровно на $$$2$$$ компоненты связности. Все города в одной компоненте принадлежат одному княжеству.

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

Если все вышесказанные условия выполняются, то разбиение на княжества возможно.