Задача о размещении бензоколонок

Формализованная постановка: Задан взвешенный граф. Найти такое минимальное подмножество вершин S, чтобы любая вершина графа была бы на расстоянии, меньшем заданного числа, от ближайшей вершины из S. 2 дня мучаюсь, добрался только до полного перебора вершин после алгоритма Флойда-Уоршелла.