Как решить эту задачу? Я пытался решить через алгоритм Краскала, но получил ТЛЕ 9. Затем использовал алгоритм Прима, но получил МЛЕ 8.
1 лайк
Ты используешь set в алгоритме Прима, в теории ты можешь добавить n^2 рёбер в set, а это n^2*log(n) времени и памяти в худшем случае.
Тебе нужно заменить set
1 лайк
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q?
Я переписал, но теперь не компилится на КФе((
Нет я не это имел ввиду.
Ты знаешь как пишется Дейкстра за O(n * m)?
Тут та же логика
1 лайк