>>221173737Он кладёт туда вершины, которое были покрашены или у них изменились метки, то есть вершины повторяются. Он может взять покрашенную вершину и что-нибудь запороть, но я же подсознательно понимаю, что это бред, но доказать не могу...
>>221173385 (OP)Скорей всего это обход в ширину и без это строчки работать не будет,как будто сложно алгоритм загуглить
>>221173857Там копии везде, хуле он попортит то? Алсо поработай над стилем оформления кода, это пиздос какой-то
>>221174079Но блять я всё равно сомневаюсь, у меня уже на этой почве крыша подтекает. Я знаю, что у помеченных вершин метки не увеличиваются, но он может у других запороть... Хоть это и невозможно, но исключать такую ситуацию нельзя.
>>221174146Даже для себя привыкни нормально код писать, если хочешь быть погромистом. Не говнокодь никогда
Не смотря на то, что оно выдало правильные ответы уже на 40 тестов, там всё равно может быть неправильно...
>>2211745031. Неговорящие названия переменных2. Директива using namespaceХотя в твоем случае простительно, иначе у тебя двух мониторов не хватит это читать
>>221174503Однобуквенные переменные, громоздкие непонятные типы. Типы лучше затайпдефить в что-нибудь с нормальными именами, переменные тоже нормально обозвать
>>221174503Да нормально там всё, анон выше просто промпрог петух, не слушай его. Олсо вместо того, чтобы спрашивать советов на дваче гугляй как устроены stl структуры и очередь твоя конкретно - и будет тебе счастье.
>>221174768Да я знаю как устроено, просто крыша подтекает из-за того, что он кидает туда копии покрашенных вершин... Там определенно что-то не так.
>>221174996Кто в 2020 году будет считать Дейкстру за квадратичное время? Разве что какие-нибудь школьники-олимпиадники.
>>221174728Нет. Когда у тебя в проекте несколько либ ты заебешься каждый раз угадывать откуда этот priority_queue. Из стд? Из локи? Из буста?
>>2211747281.Ну да, а потом читаешь в ворнингах компилятора"variable 'fake_a' set but not used" и охуеваешьТру стори, stb_image, хотя на сях своя атмосфера.2. Выше ответили
>>221175695>>221175713Пройдись по переменным отладчиком каким-нибудь или coutов нафигач в крайнем случае
Проблем из-за выделенной строчки не будет. Код скорее всего не скомпилируется потому что Q.top() вернет std::pair, а не int. Если что-то не работает пиши, посмотрим поподробнее. Про стиль кода сейчас распишу в следующем сообщении.
>>221176113Можноvoid print(const priority_queue<zalupa>& q){for(auto& item: q)cout<<item->first<<" "item->second<<'\n';}
>>221173385 (OP)Я бы ответил в мочераторо-бототред, но там переменные из одной буквы. Я такое говно даже читать не буду.
>>221176227"нет соответствующей функции для вызова «begin(std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >&)»"
>>221176431template<typename T> void print_queue(T& q) { while(!q.empty()) { std::cout << q.top() << " "; q.pop(); } std::cout << '\n';}
>>221176073Итак, поехали.>>221176105Мне в общем-то похуй лаба это или не лаба, может кому полезно будет.Первая проблема, которая бросается в глаза конечно это using namespace std. Это плохая практика, как заметили уже некоторые аноны. Библиотеки могут переопределять некоторые названия из std и использование неймспейса приведет к конфликтам. Это довольно неприятный класс проблем. Я бы рекомендовал просто приучить себя никогда не использовать using namespace std.
Немного не по теме, но не хочу еще один тред плодить - кто-нибудь знает, что за шрифт на этой картинке?
>>221176725template<typename T1, typename T2>ostream& operator<<(ostream& out, const pair<T1,T2>& p){ out<<p->first<<" "<<p->second;return out;}>>221176834Ну, по-русски его так называют.
>>221176686>>221176705>>221176725Ой бляя как вы заебали...template<class... Args>struct PrintableQueue : std::priority_queue<Args...>{public: const auto& getCont(){return this->c;}};int main(){ //std::priority_queue<int> c1; PrintableQueue<int>c1; const auto& cont = c1.getCont(); for(auto& element:cont) { std::cout << element << " "; } std::cout << std::endl;}
>>221177092Дальше идет стиль названий переменных. Рекомендуется использовать один стиль для читаемости. Допустим называть все переменные с маленькой буквы и каждое новое слово с большой: distancesFromSrc. Или все переменные маленькими буквами с подчеркиванием между ними: distances_from_src. Это становится очень важно при увеличении количества кода. Единый стиль помогает быстрее понимать к чему относится имя.Сами названия переменным стоит давать отражающие их суть. Опять же для упрощения понимания. G -> distance_matrix, d-> distances_form_source, Q -> distance_to_vertex_queue, вроде того.
>>221177348Да... Вместо своей queue используешь принтабл, getCont вернёт контейнер(у тебя вектор с парами будет), дальше делаешь с ним че хочешь. Пиздец вы, из-за вас пришлось КОД ПИСАТЬ, копипасту с цппреф не можете под себя адаптировать, рря поп контейнер очистит, кому не похуй?
>>221177317Рассмотрим типы переменных. В коде и для вершин и для дистанций используется int. Это приводит к возможным проблемам, например с тем, чтобы понять что является чем в std::pair<int, int>. Оптимальным вариантом было бы использование типов, которые бы не разрешили свободный каст между собой. Но для компактности можно использоать менее безопасный, но более простой вариант - using. Он не оградит от некорректного присвоения вершине дистанции или наоборот, но поможет понять что имелось в виду авотором. Сравните: std::pair<int, int> и std::pair<vertex_t, distance_t>. Пара строк типа using vertex_t = int; и using distance_t = int; уже улучшают читаемость.И не используйте typedef, он устарел. Используйте using.
>>221177443Вот тебе пример плохого стиля. Чтобы понять, что имел в виду анон, мне пришлось лезть в документацию priority_queue, от которой он наследовался и узнать, что protected! член, к которому имеет доступ разработчик называется блядь 'c' и, оказывается, хранит контейнер.
>>221177734Неприятно, наверное, когда твоими портянками про манякодстайлы разрабы языка подотрутся максимум...
>>221177875Он может неправильно где-то считает... Он же туда лишние элементы добавляет... Надо разобраться...
>>221177647Остановимся на используемых структурах. Для читаемости можно было бы сделать using dist_and_vertex = std::pair<distance_t, vertex_t>. Тогда получаем std::priority_queue<dist_and_vertex, std::vector<dist_and_vertex>, std::greater<dist_and_vertex>>. Это все еще довольно громоздко, но уже чуть проще чем куча пар.Но давайте посмотрим на использование пары самой по себе. Вообще std::pair плоха тем, что ее поля называются first и second. Это ни о чем не говорящее название. Обычная структура была бы более читаемой: struct VertexDist { vertex_t vert = 0; distance_t dist = 0; }; Сравните dist_queue.top().first и dist_queue.top().vert - сразу понятно какое значение мы хотим получить и не нужно разгадывать что такое first.
>>221178269Код стандартной библиотеки мало читают... Я тебя понял... Ещё и велосипед VertexDist вместо пары предлагаешь...
>>221178170Теперь про очередь. Начнем с того, что вместо queue.push(std::make_pair(a, b,)) можно использовать queue.emplace(a, b) - гораздо приятнее и компактнее.std::priority_queue, вообще говоря, я не могу назвать особенно хорошим контейнером. У нее довольно неудобный интерфейс и потенциально проблемы с производительностью. Так как низлежащий контейнер это вектор при добавлении он может расширяться, а это занимает много времени. Для чего вообще используется приоритетная очередь? Ради O(1) доступа к макс элементу и O(log_n) вставки и удаления. Знаете что еще обладает таким же свойством? std::set, при этом он удобнее и по нему можно итерироваться без извращений, которыми занимались аноны в сообщениях выше. Потенциально он быстрее - std::set не занимается релокациями, в нем нет непрерывного хранилища. Стоит проверить, не будет ли он быстрее. Но я бы рекомендовал его больше, чем std::priority_queue если это не приведет к явным проблемам с производительностью.На этом пожалуй все. Это не все проблемы с std::priority_queue, но на них подробнее останавливаться не станем.
>>221178173Ну допустим...1 6{ [1](7) [2](9) [5](14) }{ [2](9) [5](14) [3](22) }{ [5](11) [5](14) [3](20) [3](22) }{ [5](14) [3](20) [4](20) [3](22) }{ [3](20) [4](20) [3](22) }{ [4](20) [3](22) }{ [3](22) }{ }11
>>221178753>Знаете что еще обладает таким же свойством? std::set, при этом он удобнее и по нему можно итерироваться без извращений, которыми занимались аноны в сообщениях выше. Вот только в set не может быть одинаковых ключей... А реаллокация в векторе раз в 500 лет происходит, если его достаточно большим взять...
>>221178308Он пишется довольно просто: bool operator<(const VertexDist& that) const { return std::tie(distance, vertex) < std::tie(that->distance, that->vertex);}Но я бы скорее всего рекомендовал использовать свой оператор определенный около самой очереди. Дело в том, что сравнение дистанции в первую очередь не является важным свойством для общего оператора сравнения, но очень важно для конкретно этой очереди. Это опасно, поэтому лучше определить оператор специально для использования в очереди. Это лишнее в данном коде, где структура может быть определена рядом с очередью, но в реальных проектах поможет избежать возможных проблем.
>>221179004Ответ - да... Но тут элементы покрашенные повторяются... он их потом выбрасывает... вот думаю костыль сделать...
>>221173385 (OP)хуйня какая-то, у тебя в куче должны быть элементы уникальны по ключу и только делаться decrease_key если найден путь короче, ты делаешь пуш в кучу не проверяя не хуйню ли ты туда засовываешь, мб там уже путь есть лучше, вот набросал примерный код на непонятном языке:void dijkstra(from) { var remaining_vertices = new Heap(vertices); remaining_vertices[from] = 0; while (remaining_vertices.any()) { var min = remaining_vertices().pop(); dist[min.id] = min.key; for (var v in edges[min.id]) { remaining_vertices.decrease_key(v.id, min.key + v.weight); } } return dist;}
>>221179359Узнай... Если повторяются, то всё нормально... А если нет, то тогда переделай, чтобы не повторялось...
>>221178967В данном случае нет смысла в неуникальных парах вершина/дистанция. Про взять вектор согласен, но нужно сначала отнаследоваться от std::priority_queue и выделить память. Довольно громоздко и если не оправдывается производительностью, то нет смысла. Конечно же все нужно замерять.
>>221179492>В данном случае нет смысла в неуникальных парах вершина/дистанцияПочему...>но нужно сначала отнаследоваться от std::priority_queue и выделить память.Что... Я имел ввиду взять вектор как underlying контейнер в prioirity_queue... Куда наследоваться... Зачем...
>>221178205Код стандартной библиотеки плюсов это не пример читаемости и там есть специальные ограничения и исторические причины. Для обычного же кода то, что я расписал, является стандартными вещами. Все мои комментарии вполне применимы и к реальным проектам.
>>221179587Вектор и так ялвяется underlying контейнером стандартно. Для того, чтобы получить доступ к экземпляру используемого вектора придется наследоваться, так как он protected. См. >>221177257
>>221179929Это следует из логики алгоритма - берем вершину с самым коротким известным расстоянием и смотрим расстояния от нее. Если мы добавим в очередь одну и ту же вершину и расстояние, то мы просто два раза рассмотрим одни и те же пути из нее - это не имеет смысла.
>>221179359>>221179400Навскидку - чтобы определить, что элемент в очереди повторился и пропустить его достаточно:auto u = Q.top();
>>221180526Ну вон же челик написал, что они вообще повторяться не должны, если алгоритм нормально написан...
>>221180586При выполнении условия уникальности по ключу в куче да. Обычная std::priority_queue этого не позволяет просто так сделать
>>221180642У меня просто сообщения отправлялись прежде чем я их допечатывал, поэтому на несколько размазалось
>>221180760Да причём тут контейнер... В графе не может быть разных вершин с одинаковым именем и расстоянием до данной, если по какой-то причине мы такую записали, хотя у нас уже есть такая, то алгоритм неправильный...
>>221181150В графе нет, в очереди может появиться одна и та же вершина с разными расстояниями: рассмотрим ребра a, b cС расстояниями:a->c 5a->b 3b->c 1Начиная из a в очередь добавятся:c, 5b, 3По приоритету будет взята b, из b идет ребро в c, тогда в очередь добавится c, 4:c, 4c, 5У нас возникло повторение вершины в очереди. Мы могли бы избежать этого если бы был простой способ определить, что c уже в очереди и поменять его приоритет. Этого в стандартной приоритетной очереди сделать нельзя.
>>221181623>У нас возникло повторение вершины в очереди.Не повторение вершины, а повторение пары (вершина, расстояние)...>В графе не может быть разных вершин с одинаковым именем и расстоянием
>>221181805Верно. Я уточнял ситуацию, которая возникала в>>221178877>>221179155Там нет дупликации пар, только вершин
>>221181920Погоди, но приоритет-то это расстояние как раз, там могут быть вершины с разными именами и одинаковыми расстояниями, сет точно не подойдёт.
>>221182402Приоритет это расстояние в алгоритме. В коде приоритет это пара расстояние/номер вершины. Пара сравнивается сначала по расстоянию, потом по номеру вершины, поэтому приоритетеная очередь и срабатывает. Set сработает точно так же. Ключом выступает пара, а не только расстояние.Конкретные проблемы читаемости кода, которые и приводят к такому недопониманию я рассмотрел здесь, кстати:>>221179150
>>221182601>Ключом выступает пара, а не только расстояние.Если ключ это пара, то никаких проблем нет, так как одинаковых пар нет.
>>221182646Именно. Я и пытался показать, что в данном коде нет проблема корректности из-за дупликации, но есть проблема читаемости.
>>221178775Ты давно видел на cppreference полные сорцы той же пары?То, что они выставляют интерфейс на обозрение понятно, на то он интерфейс.
