Из-за этой строчки могут быть большие проблемы или я себя накручиваю? Мне страшно.
бамп
из-за этого языка могут быть проблемы с безопасностью
лучше учи Rust, за ним будущее
бамп
Хуйня ваш раст без задач
А какие проблемы ты ожидаешь?
>Rust
>безопасность
/0
Он кладёт туда вершины, которое были покрашены или у них изменились метки, то есть вершины повторяются. Он может взять покрашенную вершину и что-нибудь запороть, но я же подсознательно понимаю, что это бред, но доказать не могу...
бамп
>Q
>G
>u
>v
Погромисты 2020 подъехали.
бамп
Скорей всего это обход в ширину и без это строчки работать не будет,как будто сложно алгоритм загуглить
Там копии везде, хуле он попортит то? Алсо поработай над стилем оформления кода, это пиздос какой-то
бамп
Школьник, ты?
Так это мой код, он кроме меня нахуй никому не нужен.
Но блять я всё равно сомневаюсь, у меня уже на этой почве крыша подтекает. Я знаю, что у помеченных вершин метки не увеличиваются, но он может у других запороть... Хоть это и невозможно, но исключать такую ситуацию нельзя.
Даже для себя привыкни нормально код писать, если хочешь быть погромистом. Не говнокодь никогда
>помеченных
Покрашенных, точнее.
Дейкстра унижает битарда в собственном редакторе, спешите видеть!
Вкатывальщик, ты? Как сосётся?
Какая-то универская лаба, очевидно
Тогда тебе паранойю лечить надо, у тебя с башкой бида а не с кодом. Тут я помочь не могу
Не смотря на то, что оно выдало правильные ответы уже на 40 тестов, там всё равно может быть неправильно...
А разве не пушбэк, priority_queue над вектором же?
Оно само пушбэкает.
А что не так с оформлением кода на пикрилле, можешь, пожалуйста, объяснить?
1. Неговорящие названия переменных
2. Директива using namespace
Хотя в твоем случае простительно, иначе у тебя двух мониторов не хватит это читать
Я уже думаю свою кучу написать, чтоб точно всё разузнать.
Не ОП спрашивал.
Однобуквенные переменные, громоздкие непонятные типы. Типы лучше затайпдефить в что-нибудь с нормальными именами, переменные тоже нормально обозвать
Поколение навального, хули хотел
Поздравляю
1. Краткость сестра таланта.
2. Ты не свихнёшься писать каждый раз std :: %name%?
Да нормально там всё, анон выше просто промпрог петух, не слушай его. Олсо вместо того, чтобы спрашивать советов на дваче гугляй как устроены stl структуры и очередь твоя конкретно - и будет тебе счастье.
нет
Джун-хуебес, не открывавший Кормена, ты?
Да я знаю как устроено, просто крыша подтекает из-за того, что он кидает туда копии покрашенных вершин... Там определенно что-то не так.
Что это за говно?
Вкатывайся в какие-то менее стрессовые профессии
господи иисусе, что это за хуйня?
>algo
>dijkstra
догадайся
Кто в 2020 году будет считать Дейкстру за квадратичное время? Разве что какие-нибудь школьники-олимпиадники.
Это алгоритм Дейкстры.
Нет. Когда у тебя в проекте несколько либ ты заебешься каждый раз угадывать откуда этот priority_queue. Из стд? Из локи? Из буста?
Бамп
Как бы у опа тоже квадрат .
Бамп
Потому что ОП криворукий хуесос, очевидно же.
>priority_queue
>O(n^2)
Значение знаешь?
Впрочем не ебу , какая сложность может быть еще
Бамп
Нормальные люди за O (n log n) делают
Не, я не о том. На какой ебанине это написано?
руби-пайтон-кун
Хуи сосёшь?
Риторический вопрос
%libname% :: %funame%
На с++, не видишь чтоле?
1.Ну да, а потом читаешь в ворнингах компилятора
"variable 'fake_a' set but not used" и охуеваешь
Тру стори, stb_image, хотя на сях своя атмосфера.
2. Выше ответили
Аноны, почему тут все друг друга оскорбляют, а мне так никто не помог... Что я вам плохого сделал...
Бамп
А чем тебе помочь-то, няша?
Нужно понять, где я ошибся...
Я не понимаю где, но я точно где-то ошибся...
Бамп
Бамп
Что конкретно тебя смущает?
Пройдись по переменным отладчиком каким-нибудь или coutов нафигач в крайнем случае
А лучше покрой нормальными тестами и успокойся
Проблем из-за выделенной строчки не будет. Код скорее всего не скомпилируется потому что Q.top() вернет std::pair, а не int. Если что-то не работает пиши, посмотрим поподробнее. Про стиль кода сейчас распишу в следующем сообщении.
> Про стиль кода сейчас распишу в следующем сообщении.
Нет смысла, это лаба.
Приоритетную очередь нельзя вывести.
В каком это смысле нельзя?
Я просто убрал .second у пары, потому что он мне не нравится...
Можно
void print(const priority_queue<zalupa>& q)
{
for(auto& item: q)cout<<item->first<<" "item->second<<'\n';
}
Я бы ответил в мочераторо-бототред, но там переменные из одной буквы. Я такое говно даже читать не буду.
Наркоман? Ёбом токнуть?
Зачем это моче?
"нет соответствующей функции для вызова «begin(std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >&)»"
бамп
бамп
template<typename T> void print_queue(T& q) {
while(!q.empty()) {
std::cout << q.top() << " ";
q.pop();
}
std::cout << '\n';
}
А зачем её по ссылке передавать? Она же удалится вся...
Блин, не знал.
Я думаю, лучше по значению передавать
Плохой вариант, очищает контейнер. Плюс пару просто так не запишешь в поток
Переопределить оператор вывода для пары не выйдет?
бамп...
>оператор вывода
>оператор
>вывода
Аноны, хватит спорить, помогли бы уже...
бамп
Итак, поехали.
Мне в общем-то похуй лаба это или не лаба, может кому полезно будет.
Первая проблема, которая бросается в глаза конечно это using namespace std. Это плохая практика, как заметили уже некоторые аноны. Библиотеки могут переопределять некоторые названия из std и использование неймспейса приведет к конфликтам. Это довольно неприятный класс проблем. Я бы рекомендовал просто приучить себя никогда не использовать using namespace std.
Немного не по теме, но не хочу еще один тред плодить - кто-нибудь знает, что за шрифт на этой картинке?
бамп
template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1,T2>& p)
{
out<<p->first<<" "<<p->second;
return out;
}
Ну, по-русски его так называют.
Как ты проверяешь , что уже посетил вершину ?
Ой бляя как вы заебали...
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;
}
Дальше идет стиль названий переменных. Рекомендуется использовать один стиль для читаемости. Допустим называть все переменные с маленькой буквы и каждое новое слово с большой: distancesFromSrc. Или все переменные маленькими буквами с подчеркиванием между ними: distances_from_src. Это становится очень важно при увеличении количества кода. Единый стиль помогает быстрее понимать к чему относится имя.
Сами названия переменным стоит давать отражающие их суть. Опять же для упрощения понимания. G -> distance_matrix, d-> distances_form_source, Q -> distance_to_vertex_queue, вроде того.
А эта программа скомпилируется?
> this->c
Охуительный код-стайл от авторов STL
Да... Вместо своей queue используешь принтабл, getCont вернёт контейнер(у тебя вектор с парами будет), дальше делаешь с ним че хочешь. Пиздец вы, из-за вас пришлось КОД ПИСАТЬ, копипасту с цппреф не можете под себя адаптировать, рря поп контейнер очистит, кому не похуй?
Что...
бамп....
Рассмотрим типы переменных. В коде и для вершин и для дистанций используется 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.
Вот тебе пример плохого стиля. Чтобы понять, что имел в виду анон, мне пришлось лезть в документацию priority_queue, от которой он наследовался и узнать, что protected! член, к которому имеет доступ разработчик называется блядь 'c' и, оказывается, хранит контейнер.
И что... Не знаешь стандарт — твои проблемы...
Иди нахуй...
Неприятно, наверное, когда твоими портянками про манякодстайлы разрабы языка подотрутся максимум...
Аноны, не тролльте меня пожалуйста... У меня тут реальная проблема...
В чём она заключается?
В душе не ебу, чем они там подтираются, это в принципе специфичные люди
Сишный макаки это потеха какая-то.
Ну явно поумнее маминого умника с двачей...
Он может неправильно где-то считает... Он же туда лишние элементы добавляет... Надо разобраться...
>Он же туда лишние элементы добавляет...
Почему ты так решил?
Блять, дак запусти тест, проверь.
Потому что это действительно так...
Я запускал и не раз, он выдаёт правильные ответы...
Остановимся на используемых структурах. Для читаемости можно было бы сделать 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.
Это не ответ... Ты распечатал очередь?
Зачем ты это пишешь... Даже разрабы языков этой хипстерской хуйни не придердживаются...
Ёб... Вашу... Мать...
Разрабам похуй, их код мало читают
В твоей VertexDist не хватает оператора сравнения
Код стандартной библиотеки мало читают... Я тебя понял... Ещё и велосипед VertexDist вместо пары предлагаешь...
Да, нормальные люди заходят на cpp-reference и читают документацию
Ну так на cppreference и написано про контейнер c...
Ну вот если бы его назвали хотя бы container, мне бы не пришлось это читать вообще
Теперь про очередь. Начнем с того, что вместо 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, но на них подробнее останавливаться не станем.
Ну так ты выше писал, что их код никто не читает... Выходит все читают...
Ну допустим...
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
>Знаете что еще обладает таким же свойством? std::set, при этом он удобнее и по нему можно итерироваться без извращений, которыми занимались аноны в сообщениях выше.
Вот только в set не может быть одинаковых ключей... А реаллокация в векторе раз в 500 лет происходит, если его достаточно большим взять...
И как... Всё правильно?
Он пишется довольно просто: bool operator<(const VertexDist& that) const {
return std::tie(distance, vertex) < std::tie(that->distance, that->vertex);
}
Но я бы скорее всего рекомендовал использовать свой оператор определенный около самой очереди. Дело в том, что сравнение дистанции в первую очередь не является важным свойством для общего оператора сравнения, но очень важно для конкретно этой очереди. Это опасно, поэтому лучше определить оператор специально для использования в очереди. Это лишнее в данном коде, где структура может быть определена рядом с очередью, но в реальных проектах поможет избежать возможных проблем.
Ответ - да... Но тут элементы покрашенные повторяются... он их потом выбрасывает... вот думаю костыль сделать...
Нет, не выходит
Ну тебе виднее...
бамп...
хуйня какая-то, у тебя в куче должны быть элементы уникальны по ключу и только делаться 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;
}
Поправка: будет не ->, а . потому что передали через ссылку, но суть не меняется.
А по алгоритму они должны повторяться? Или нет...
Конечно, виднее.
не знаю...
Узнай... Если повторяются, то всё нормально... А если нет, то тогда переделай, чтобы не повторялось...
Это был сарказм...
В данном случае нет смысла в неуникальных парах вершина/дистанция. Про взять вектор согласен, но нужно сначала отнаследоваться от std::priority_queue и выделить память. Довольно громоздко и если не оправдывается производительностью, то нет смысла. Конечно же все нужно замерять.
>В данном случае нет смысла в неуникальных парах вершина/дистанция
Почему...
>но нужно сначала отнаследоваться от std::priority_queue и выделить память.
Что... Я имел ввиду взять вектор как underlying контейнер в prioirity_queue... Куда наследоваться... Зачем...
Не ебу што эта, ёбана
Код стандартной библиотеки плюсов это не пример читаемости и там есть специальные ограничения и исторические причины. Для обычного же кода то, что я расписал, является стандартными вещами. Все мои комментарии вполне применимы и к реальным проектам.
Вектор и так ялвяется underlying контейнером стандартно. Для того, чтобы получить доступ к экземпляру используемого вектора придется наследоваться, так как он protected. См.
Понятно... А что с
>В данном случае нет смысла в неуникальных парах вершина/дистанция
Ну хоть не js
Это следует из логики алгоритма - берем вершину с самым коротким известным расстоянием и смотрим расстояния от нее. Если мы добавим в очередь одну и ту же вершину и расстояние, то мы просто два раза рассмотрим одни и те же пути из нее - это не имеет смысла.
Логично...
Ну да...
Навскидку - чтобы определить, что элемент в очереди повторился и пропустить его достаточно:
auto u = Q.top();
Q.pop();
if (u.first > d) continue;
Да ебаный в рот
Ну вон же челик написал, что они вообще повторяться не должны, если алгоритм нормально написан...
if (u.first > d[u.second]) continue;
ну дак нормальных кодеров не осталось
При выполнении условия уникальности по ключу в куче да. Обычная std::priority_queue этого не позволяет просто так сделать
У меня просто сообщения отправлялись прежде чем я их допечатывал, поэтому на несколько размазалось
Да причём тут контейнер... В графе не может быть разных вершин с одинаковым именем и расстоянием до данной, если по какой-то причине мы такую записали, хотя у нас уже есть такая, то алгоритм неправильный...
В графе нет, в очереди может появиться одна и та же вершина с разными расстояниями: рассмотрим ребра a, b c
С расстояниями:
a->c 5
a->b 3
b->c 1
Начиная из a в очередь добавятся:
c, 5
b, 3
По приоритету будет взята b, из b идет ребро в c, тогда в очередь добавится c, 4:
c, 4
c, 5
У нас возникло повторение вершины в очереди. Мы могли бы избежать этого если бы был простой способ определить, что c уже в очереди и поменять его приоритет. Этого в стандартной приоритетной очереди сделать нельзя.
Ну так алгоритм про обход графа же...
>У нас возникло повторение вершины в очереди.
Не повторение вершины, а повторение пары (вершина, расстояние)...
>В графе не может быть разных вершин с одинаковым именем и расстоянием
Верно. Я уточнял ситуацию, которая возникала в
Там нет дупликации пар, только вершин
Погоди, но приоритет-то это расстояние как раз, там могут быть вершины с разными именами и одинаковыми расстояниями, сет точно не подойдёт.
Приоритет это расстояние в алгоритме. В коде приоритет это пара расстояние/номер вершины. Пара сравнивается сначала по расстоянию, потом по номеру вершины, поэтому приоритетеная очередь и срабатывает. Set сработает точно так же. Ключом выступает пара, а не только расстояние.
Конкретные проблемы читаемости кода, которые и приводят к такому недопониманию я рассмотрел здесь, кстати:
>Ключом выступает пара, а не только расстояние.
Если ключ это пара, то никаких проблем нет, так как одинаковых пар нет.
пиши на си сам свой стек хуль тут ебатня какая-то
Именно. Я и пытался показать, что в данном коде нет проблема корректности из-за дупликации, но есть проблема читаемости.
По-моему ты только всех запутал.
Ты давно видел на cppreference полные сорцы той же пары?
То, что они выставляют интерфейс на обозрение понятно, на то он интерфейс.
