Я работаю над решением следующей проблемы и реализую решение в C ++.
Предположим, что у нас есть ориентированный взвешенный граф G = (V, A, w) и P множество людей.
Мы получаем такое количество запросов, что каждый запрос дает человеку p и две вершины s и d и просит вычислить минимальный взвешенный путь между s и d для человека p.Один человек может иметь несколько путей.
После окончания всех запросов у меня есть число k <= | A |и я должен дать k дуг так, чтобы число людей, использующих хотя бы одну из k дуг, было максимальным (это проблема максимального покрытия).</p>
Для решения первой части я реализовал алгоритм Джикистры с использованием priority_queue и вычисляю минимальный вес между s и d.(Это хороший способ сделать?)
Чтобы решить вторую часть, я сохраняю для каждой дуги набор людей, которые используют эту дугу, и я использую жадный алгоритм для вычисления набора дуг (на каждом этапеЯ выбираю дугу, используемую наибольшим числом непокрытых лиц).(Это хороший способ сделать это?)
Наконец, если мои алгоритмы - это товар, как я могу эффективно реализовать их в C ++?