Добавлю в “копилку алгоритма” - если расстояние между “узлом мажора” и целью больше 160 км, то есть повод подумать про мажоры.
Пример Иваново возмем за центр. Рисуем окружность в 100-150км. Дороги до целей в радиусе “до” - миноры, “после” - мажоры. Получается вся область - достаточно миноров. Варианты до Ярославля, Владимира, Костромы, Нижнего - нужны мажоры. И так на каждом “узле”.