Сохранен 175
https://2ch.hk/b/res/221173385.html
24 декабря 2023 г. Архивач восстановлен после серьёзной аварии. К сожалению, значительная часть сохранённых изображений и видео была потеряна. Подробности случившегося. Мы призываем всех неравнодушных помочь нам с восстановлением утраченного контента!
Аноним 26/05/20 Втр 23:21:03 #1 №221173385 
изображение.png
Из-за этой строчки могут быть большие проблемы или я себя накручиваю? Мне страшно.
Аноним 26/05/20 Втр 23:24:01 #2 №221173581 
бамп
Аноним 26/05/20 Втр 23:24:55 #3 №221173631 
>>221173385 (OP)
из-за этого языка могут быть проблемы с безопасностью

лучше учи Rust, за ним будущее
Аноним 26/05/20 Втр 23:26:32 #4 №221173729 
бамп
Аноним 26/05/20 Втр 23:26:44 #5 №221173737 
>>221173631
Хуйня ваш раст без задач

>>221173385 (OP)
А какие проблемы ты ожидаешь?
Аноним 26/05/20 Втр 23:27:01 #6 №221173757 
>>221173631
>Rust
>безопасность
/0
Аноним 26/05/20 Втр 23:28:50 #7 №221173857 
>>221173737
Он кладёт туда вершины, которое были покрашены или у них изменились метки, то есть вершины повторяются. Он может взять покрашенную вершину и что-нибудь запороть, но я же подсознательно понимаю, что это бред, но доказать не могу...
Аноним 26/05/20 Втр 23:30:11 #8 №221173941 
бамп
sageАноним 26/05/20 Втр 23:30:14 #9 №221173943 
>>221173385 (OP)
>Q
>G
>u
>v
Погромисты 2020 подъехали.
Аноним 26/05/20 Втр 23:31:30 #10 №221174023 
бамп
Аноним 26/05/20 Втр 23:31:44 #11 №221174039 
>>221173385 (OP)
Скорей всего это обход в ширину и без это строчки работать не будет,как будто сложно алгоритм загуглить
Аноним 26/05/20 Втр 23:32:16 #12 №221174079 
>>221173857
Там копии везде, хуле он попортит то? Алсо поработай над стилем оформления кода, это пиздос какой-то
Аноним 26/05/20 Втр 23:32:28 #13 №221174092 
бамп
Аноним 26/05/20 Втр 23:33:04 #14 №221174130 
>>221174039
Школьник, ты?
Аноним 26/05/20 Втр 23:33:28 #15 №221174146 
>>221174079
Так это мой код, он кроме меня нахуй никому не нужен.
Аноним 26/05/20 Втр 23:35:12 #16 №221174301 
>>221174079
Но блять я всё равно сомневаюсь, у меня уже на этой почве крыша подтекает. Я знаю, что у помеченных вершин метки не увеличиваются, но он может у других запороть... Хоть это и невозможно, но исключать такую ситуацию нельзя.
Аноним 26/05/20 Втр 23:35:16 #17 №221174306 
>>221174146
Даже для себя привыкни нормально код писать, если хочешь быть погромистом. Не говнокодь никогда
Аноним 26/05/20 Втр 23:35:37 #18 №221174324 
>>221174301
>помеченных
Покрашенных, точнее.
Аноним 26/05/20 Втр 23:35:51 #19 №221174346 
image.png
>>221173385 (OP)
Дейкстра унижает битарда в собственном редакторе, спешите видеть!
Аноним 26/05/20 Втр 23:36:28 #20 №221174387 
>>221173943
Вкатывальщик, ты? Как сосётся?
Аноним 26/05/20 Втр 23:36:51 #21 №221174413 
>>221173943
Какая-то универская лаба, очевидно
Аноним 26/05/20 Втр 23:37:03 #22 №221174429 
>>221174301
Тогда тебе паранойю лечить надо, у тебя с башкой бида а не с кодом. Тут я помочь не могу
Аноним 26/05/20 Втр 23:37:07 #23 №221174433 
Не смотря на то, что оно выдало правильные ответы уже на 40 тестов, там всё равно может быть неправильно...
Аноним 26/05/20 Втр 23:37:49 #24 №221174483 
А разве не пушбэк, priority_queue над вектором же?
Аноним 26/05/20 Втр 23:38:07 #25 №221174501 
>>221174483
Оно само пушбэкает.
Аноним 26/05/20 Втр 23:38:12 #26 №221174503 
>>221174306
А что не так с оформлением кода на пикрилле, можешь, пожалуйста, объяснить?
Аноним 26/05/20 Втр 23:40:02 #27 №221174602 
>>221174503
1. Неговорящие названия переменных
2. Директива using namespace
Хотя в твоем случае простительно, иначе у тебя двух мониторов не хватит это читать
Аноним 26/05/20 Втр 23:40:04 #28 №221174604 
Я уже думаю свою кучу написать, чтоб точно всё разузнать.
Аноним 26/05/20 Втр 23:40:43 #29 №221174651 
>>221174602
Не ОП спрашивал.
Аноним 26/05/20 Втр 23:40:51 #30 №221174658 
>>221174503
Однобуквенные переменные, громоздкие непонятные типы. Типы лучше затайпдефить в что-нибудь с нормальными именами, переменные тоже нормально обозвать
Аноним 26/05/20 Втр 23:41:23 #31 №221174692 
>>221173943
Поколение навального, хули хотел
Аноним 26/05/20 Втр 23:41:28 #32 №221174699 
>>221174651
Поздравляю
Аноним 26/05/20 Втр 23:42:04 #33 №221174728 
>>221174602
1. Краткость сестра таланта.
2. Ты не свихнёшься писать каждый раз std :: %name%?
Аноним 26/05/20 Втр 23:42:40 #34 №221174768 
>>221174503
Да нормально там всё, анон выше просто промпрог петух, не слушай его. Олсо вместо того, чтобы спрашивать советов на дваче гугляй как устроены stl структуры и очередь твоя конкретно - и будет тебе счастье.
Аноним 26/05/20 Втр 23:43:23 #35 №221174807 
>>221173385 (OP)
https://e-maxx.ru/algo/dijkstra
Аноним 26/05/20 Втр 23:43:42 #36 №221174824 
>>221174130
нет
Аноним 26/05/20 Втр 23:43:47 #37 №221174826 
>>221173943
Джун-хуебес, не открывавший Кормена, ты?
Аноним 26/05/20 Втр 23:44:14 #38 №221174847 
>>221174768
Да я знаю как устроено, просто крыша подтекает из-за того, что он кидает туда копии покрашенных вершин... Там определенно что-то не так.
Аноним 26/05/20 Втр 23:44:54 #39 №221174891 
>>221174807
Что это за говно?
Аноним 26/05/20 Втр 23:45:54 #40 №221174952 
image.png
>>221174847
Вкатывайся в какие-то менее стрессовые профессии
Аноним 26/05/20 Втр 23:46:23 #41 №221174984 
>>221173385 (OP)
господи иисусе, что это за хуйня?
Аноним 26/05/20 Втр 23:46:31 #42 №221174996 
>>221174891
>algo
>dijkstra
догадайся
Аноним 26/05/20 Втр 23:48:02 #43 №221175066 
>>221174996
Кто в 2020 году будет считать Дейкстру за квадратичное время? Разве что какие-нибудь школьники-олимпиадники.
Аноним 26/05/20 Втр 23:48:28 #44 №221175090 
>>221174984
Это алгоритм Дейкстры.
Аноним 26/05/20 Втр 23:48:36 #45 №221175101 
>>221174728
Нет. Когда у тебя в проекте несколько либ ты заебешься каждый раз угадывать откуда этот priority_queue. Из стд? Из локи? Из буста?
Аноним 26/05/20 Втр 23:48:59 #46 №221175118 
Бамп
Аноним 26/05/20 Втр 23:49:56 #47 №221175169 
>>221175066
Как бы у опа тоже квадрат .
Аноним 26/05/20 Втр 23:50:06 #48 №221175181 
Бамп
Аноним 26/05/20 Втр 23:50:31 #49 №221175202 
>>221175169
Потому что ОП криворукий хуесос, очевидно же.
Аноним 26/05/20 Втр 23:50:43 #50 №221175209 
>>221175066
>priority_queue
>O(n^2)
Значение знаешь?
Аноним 26/05/20 Втр 23:51:41 #51 №221175264 
>>221175066
>>221175169
Впрочем не ебу , какая сложность может быть еще
Аноним 26/05/20 Втр 23:53:00 #52 №221175327 
Бамп
Аноним 26/05/20 Втр 23:53:23 #53 №221175349 
>>221175264
Нормальные люди за O (n log n) делают
Аноним 26/05/20 Втр 23:53:24 #54 №221175350 
>>221175090
Не, я не о том. На какой ебанине это написано?
руби-пайтон-кун
Аноним 26/05/20 Втр 23:53:55 #55 №221175384 
>>221175350
Хуи сосёшь?
Риторический вопрос
Аноним 26/05/20 Втр 23:54:27 #56 №221175416 
>>221175101
%libname% :: %funame%
Аноним 26/05/20 Втр 23:54:28 #57 №221175422 
>>221175350
На с++, не видишь чтоле?
Аноним 26/05/20 Втр 23:55:34 #58 №221175481 
>>221174728
1.Ну да, а потом читаешь в ворнингах компилятора
"variable 'fake_a' set but not used" и охуеваешь
Тру стори, stb_image, хотя на сях своя атмосфера.
2. Выше ответили
Аноним 26/05/20 Втр 23:55:56 #59 №221175494 
Аноны, почему тут все друг друга оскорбляют, а мне так никто не помог... Что я вам плохого сделал...
Аноним 26/05/20 Втр 23:57:29 #60 №221175577 
Бамп
Аноним 26/05/20 Втр 23:57:45 #61 №221175595 
>>221175494
А чем тебе помочь-то, няша?
Аноним 26/05/20 Втр 23:59:40 #62 №221175695 
>>221175595
Нужно понять, где я ошибся...
Аноним 26/05/20 Втр 23:59:57 #63 №221175713 
Я не понимаю где, но я точно где-то ошибся...
Аноним 27/05/20 Срд 00:02:13 #64 №221175855 
Бамп
Аноним 27/05/20 Срд 00:04:03 #65 №221175964 
Бамп
Аноним 27/05/20 Срд 00:04:12 #66 №221175976 
>>221173385 (OP)
Что конкретно тебя смущает?
Аноним 27/05/20 Срд 00:04:46 #67 №221176012 
>>221175695
>>221175713
Пройдись по переменным отладчиком каким-нибудь или coutов нафигач в крайнем случае
Аноним 27/05/20 Срд 00:05:25 #68 №221176051 
А лучше покрой нормальными тестами и успокойся
Аноним 27/05/20 Срд 00:05:47 #69 №221176073 
Проблем из-за выделенной строчки не будет. Код скорее всего не скомпилируется потому что Q.top() вернет std::pair, а не int. Если что-то не работает пиши, посмотрим поподробнее. Про стиль кода сейчас распишу в следующем сообщении.
Аноним 27/05/20 Срд 00:06:19 #70 №221176105 
>>221176073
> Про стиль кода сейчас распишу в следующем сообщении.
Нет смысла, это лаба.
Аноним 27/05/20 Срд 00:06:35 #71 №221176113 
>>221176012
Приоритетную очередь нельзя вывести.
Аноним 27/05/20 Срд 00:07:49 #72 №221176175 
>>221176113
В каком это смысле нельзя?
Аноним 27/05/20 Срд 00:08:21 #73 №221176207 
>>221176073
Я просто убрал .second у пары, потому что он мне не нравится...
Аноним 27/05/20 Срд 00:08:42 #74 №221176227 
>>221176113
Можно
void print(const priority_queue<zalupa>& q)
{
for(auto& item: q)cout<<item->first<<" "item->second<<'\n';
}
Аноним 27/05/20 Срд 00:10:00 #75 №221176282 
>>221173385 (OP)
Я бы ответил в мочераторо-бототред, но там переменные из одной буквы. Я такое говно даже читать не буду.
Аноним 27/05/20 Срд 00:10:07 #76 №221176286 
>>221176207
Наркоман? Ёбом токнуть?
Аноним 27/05/20 Срд 00:11:22 #77 №221176356 
>>221176282
Зачем это моче?
Аноним 27/05/20 Срд 00:12:57 #78 №221176431 
>>221176227
"нет соответствующей функции для вызова «begin(std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >&)»"
Аноним 27/05/20 Срд 00:14:45 #79 №221176518 
бамп
Аноним 27/05/20 Срд 00:15:42 #80 №221176574 
бамп
Аноним 27/05/20 Срд 00:16:25 #81 №221176605 
15495474087751.png
15657323717680.png
ВАЙТИШНИК.png
>>221173385 (OP)
Аноним 27/05/20 Срд 00:16:42 #82 №221176616 
>>221176431
template<typename T> void print_queue(T& q) {
while(!q.empty()) {
std::cout << q.top() << " ";
q.pop();
}
std::cout << '\n';
}
Аноним 27/05/20 Срд 00:17:55 #83 №221176686 
>>221176616
А зачем её по ссылке передавать? Она же удалится вся...
Аноним 27/05/20 Срд 00:18:20 #84 №221176705 
>>221176431
Блин, не знал.
>>221176616
Я думаю, лучше по значению передавать
Аноним 27/05/20 Срд 00:18:44 #85 №221176725 
>>221176616
Плохой вариант, очищает контейнер. Плюс пару просто так не запишешь в поток
Аноним 27/05/20 Срд 00:19:53 #86 №221176783 
>>221176725
Переопределить оператор вывода для пары не выйдет?
Аноним 27/05/20 Срд 00:20:10 #87 №221176797 
бамп...
Аноним 27/05/20 Срд 00:20:51 #88 №221176834 
>>221176783
>оператор вывода
>оператор
>вывода
Аноним 27/05/20 Срд 00:22:58 #89 №221176955 
Аноны, хватит спорить, помогли бы уже...
Аноним 27/05/20 Срд 00:25:18 #90 №221177075 
бамп
Аноним 27/05/20 Срд 00:25:38 #91 №221177092 
>>221176073
Итак, поехали.
>>221176105
Мне в общем-то похуй лаба это или не лаба, может кому полезно будет.

Первая проблема, которая бросается в глаза конечно это using namespace std. Это плохая практика, как заметили уже некоторые аноны. Библиотеки могут переопределять некоторые названия из std и использование неймспейса приведет к конфликтам. Это довольно неприятный класс проблем. Я бы рекомендовал просто приучить себя никогда не использовать using namespace std.

Аноним 27/05/20 Срд 00:26:17 #92 №221177127 
image.png
Немного не по теме, но не хочу еще один тред плодить - кто-нибудь знает, что за шрифт на этой картинке?
Аноним 27/05/20 Срд 00:26:50 #93 №221177158 
бамп
Аноним 27/05/20 Срд 00:28:18 #94 №221177233 
>>221176725
template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1,T2>& p)
{
out<<p->first<<" "<<p->second;
return out;
}
>>221176834
Ну, по-русски его так называют.
Аноним 27/05/20 Срд 00:28:25 #95 №221177238 
>>221175209
Как ты проверяешь , что уже посетил вершину ?
Аноним 27/05/20 Срд 00:28:53 #96 №221177257 
>>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;
}
Аноним 27/05/20 Срд 00:30:11 #97 №221177317 
>>221177092
Дальше идет стиль названий переменных. Рекомендуется использовать один стиль для читаемости. Допустим называть все переменные с маленькой буквы и каждое новое слово с большой: distancesFromSrc. Или все переменные маленькими буквами с подчеркиванием между ними: distances_from_src. Это становится очень важно при увеличении количества кода. Единый стиль помогает быстрее понимать к чему относится имя.

Сами названия переменным стоит давать отражающие их суть. Опять же для упрощения понимания. G -> distance_matrix, d-> distances_form_source, Q -> distance_to_vertex_queue, вроде того.
Аноним 27/05/20 Срд 00:30:41 #98 №221177348 
>>221177257
А эта программа скомпилируется?
Аноним 27/05/20 Срд 00:31:46 #99 №221177404 
>>221177257
> this->c
Охуительный код-стайл от авторов STL
Аноним 27/05/20 Срд 00:32:14 #100 №221177426 
>>221177348
Да... Вместо своей queue используешь принтабл, getCont вернёт контейнер(у тебя вектор с парами будет), дальше делаешь с ним че хочешь. Пиздец вы, из-за вас пришлось КОД ПИСАТЬ, копипасту с цппреф не можете под себя адаптировать, рря поп контейнер очистит, кому не похуй?
Аноним 27/05/20 Срд 00:32:36 #101 №221177443 
>>221177404
Что...
Аноним 27/05/20 Срд 00:34:49 #102 №221177542 
бамп....
Аноним 27/05/20 Срд 00:36:50 #103 №221177647 
>>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.
Аноним 27/05/20 Срд 00:36:53 #104 №221177650 
>>221177443
Вот тебе пример плохого стиля. Чтобы понять, что имел в виду анон, мне пришлось лезть в документацию priority_queue, от которой он наследовался и узнать, что protected! член, к которому имеет доступ разработчик называется блядь 'c' и, оказывается, хранит контейнер.
Аноним 27/05/20 Срд 00:37:47 #105 №221177708 
>>221177650
И что... Не знаешь стандарт — твои проблемы...
Аноним 27/05/20 Срд 00:38:11 #106 №221177734 
>>221177708
Иди нахуй...
Аноним 27/05/20 Срд 00:39:05 #107 №221177783 
>>221177734
Неприятно, наверное, когда твоими портянками про манякодстайлы разрабы языка подотрутся максимум...
Аноним OP 27/05/20 Срд 00:39:57 #108 №221177834 
Аноны, не тролльте меня пожалуйста... У меня тут реальная проблема...
Аноним 27/05/20 Срд 00:40:39 #109 №221177875 
>>221177834
В чём она заключается?
Аноним 27/05/20 Срд 00:41:30 #110 №221177924 
>>221177783
В душе не ебу, чем они там подтираются, это в принципе специфичные люди
Аноним 27/05/20 Срд 00:42:05 #111 №221177962 
Сишный макаки это потеха какая-то.
Аноним 27/05/20 Срд 00:42:16 #112 №221177967 
>>221177924
Ну явно поумнее маминого умника с двачей...
Аноним OP 27/05/20 Срд 00:42:25 #113 №221177971 
>>221177875
Он может неправильно где-то считает... Он же туда лишние элементы добавляет... Надо разобраться...
Аноним 27/05/20 Срд 00:42:50 #114 №221177992 
>>221177971
>Он же туда лишние элементы добавляет...
Почему ты так решил?
Аноним 27/05/20 Срд 00:44:07 #115 №221178046 
>>221177971
Блять, дак запусти тест, проверь.
Аноним OP 27/05/20 Срд 00:45:59 #116 №221178142 
>>221177992
Потому что это действительно так...
Аноним OP 27/05/20 Срд 00:46:23 #117 №221178164 
>>221178046
Я запускал и не раз, он выдаёт правильные ответы...
Аноним 27/05/20 Срд 00:46:31 #118 №221178170 
>>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.
Аноним 27/05/20 Срд 00:46:35 #119 №221178173 
>>221178142
Это не ответ... Ты распечатал очередь?
Аноним 27/05/20 Срд 00:47:18 #120 №221178205 
>>221178170
Зачем ты это пишешь... Даже разрабы языков этой хипстерской хуйни не придердживаются...
Аноним 27/05/20 Срд 00:47:34 #121 №221178224 
Ёб... Вашу... Мать...
Аноним 27/05/20 Срд 00:48:25 #122 №221178269 
>>221178205
Разрабам похуй, их код мало читают
Аноним 27/05/20 Срд 00:49:20 #123 №221178308 
>>221178170
В твоей VertexDist не хватает оператора сравнения
Аноним 27/05/20 Срд 00:50:03 #124 №221178355 
>>221178269
Код стандартной библиотеки мало читают... Я тебя понял... Ещё и велосипед VertexDist вместо пары предлагаешь...
Аноним 27/05/20 Срд 00:51:40 #125 №221178449 
>>221178355
Да, нормальные люди заходят на cpp-reference и читают документацию
Аноним 27/05/20 Срд 00:53:19 #126 №221178527 
>>221178449
Ну так на cppreference и написано про контейнер c...
Аноним 27/05/20 Срд 00:57:19 #127 №221178715 
>>221178527
Ну вот если бы его назвали хотя бы container, мне бы не пришлось это читать вообще
Аноним 27/05/20 Срд 00:57:50 #128 №221178753 
>>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, но на них подробнее останавливаться не станем.
Аноним 27/05/20 Срд 00:58:11 #129 №221178775 
>>221178715
Ну так ты выше писал, что их код никто не читает... Выходит все читают...
Аноним OP 27/05/20 Срд 00:59:56 #130 №221178877 
>>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
Аноним 27/05/20 Срд 01:01:34 #131 №221178967 
>>221178753
>Знаете что еще обладает таким же свойством? std::set, при этом он удобнее и по нему можно итерироваться без извращений, которыми занимались аноны в сообщениях выше.
Вот только в set не может быть одинаковых ключей... А реаллокация в векторе раз в 500 лет происходит, если его достаточно большим взять...
Аноним 27/05/20 Срд 01:02:12 #132 №221179004 
>>221178877
И как... Всё правильно?
Аноним 27/05/20 Срд 01:04:38 #133 №221179150 
>>221178308
Он пишется довольно просто: bool operator<(const VertexDist& that) const {
return std::tie(distance, vertex) < std::tie(that->distance, that->vertex);
}

Но я бы скорее всего рекомендовал использовать свой оператор определенный около самой очереди. Дело в том, что сравнение дистанции в первую очередь не является важным свойством для общего оператора сравнения, но очень важно для конкретно этой очереди. Это опасно, поэтому лучше определить оператор специально для использования в очереди. Это лишнее в данном коде, где структура может быть определена рядом с очередью, но в реальных проектах поможет избежать возможных проблем.
Аноним OP 27/05/20 Срд 01:04:44 #134 №221179155 
>>221179004
Ответ - да... Но тут элементы покрашенные повторяются... он их потом выбрасывает... вот думаю костыль сделать...
Аноним 27/05/20 Срд 01:04:44 #135 №221179156 
>>221178775
Нет, не выходит
Аноним 27/05/20 Срд 01:06:36 #136 №221179239 
>>221179156
Ну тебе виднее...
Аноним OP 27/05/20 Срд 01:07:00 #137 №221179262 
бамп...
Аноним 27/05/20 Срд 01:07:15 #138 №221179279 
>>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;
}
Аноним 27/05/20 Срд 01:07:54 #139 №221179309 
>>221179150
Поправка: будет не ->, а . потому что передали через ссылку, но суть не меняется.
Аноним 27/05/20 Срд 01:08:42 #140 №221179341 
>>221179155
А по алгоритму они должны повторяться? Или нет...
Аноним 27/05/20 Срд 01:08:44 #141 №221179344 
>>221179239
Конечно, виднее.
Аноним OP 27/05/20 Срд 01:09:08 #142 №221179359 
>>221179341
не знаю...
Аноним 27/05/20 Срд 01:10:00 #143 №221179400 
>>221179359
Узнай... Если повторяются, то всё нормально... А если нет, то тогда переделай, чтобы не повторялось...
Аноним 27/05/20 Срд 01:10:23 #144 №221179420 
>>221179344
Это был сарказм...
Аноним 27/05/20 Срд 01:11:39 #145 №221179492 
>>221178967
В данном случае нет смысла в неуникальных парах вершина/дистанция. Про взять вектор согласен, но нужно сначала отнаследоваться от std::priority_queue и выделить память. Довольно громоздко и если не оправдывается производительностью, то нет смысла. Конечно же все нужно замерять.
Аноним 27/05/20 Срд 01:13:35 #146 №221179587 
>>221179492
>В данном случае нет смысла в неуникальных парах вершина/дистанция
Почему...
>но нужно сначала отнаследоваться от std::priority_queue и выделить память.
Что... Я имел ввиду взять вектор как underlying контейнер в prioirity_queue... Куда наследоваться... Зачем...
Аноним 27/05/20 Срд 01:13:56 #147 №221179607 
>>221173385 (OP)
Не ебу што эта, ёбана
Аноним 27/05/20 Срд 01:15:18 #148 №221179686 
>>221178205
Код стандартной библиотеки плюсов это не пример читаемости и там есть специальные ограничения и исторические причины. Для обычного же кода то, что я расписал, является стандартными вещами. Все мои комментарии вполне применимы и к реальным проектам.
Аноним 27/05/20 Срд 01:18:24 #149 №221179857 
>>221179587
Вектор и так ялвяется underlying контейнером стандартно. Для того, чтобы получить доступ к экземпляру используемого вектора придется наследоваться, так как он protected. См. >>221177257
Аноним 27/05/20 Срд 01:19:54 #150 №221179929 
>>221179857
Понятно... А что с
>В данном случае нет смысла в неуникальных парах вершина/дистанция
Аноним 27/05/20 Срд 01:21:17 #151 №221179990 
Ну хоть не js
Аноним 27/05/20 Срд 01:22:33 #152 №221180057 
>>221179929
Это следует из логики алгоритма - берем вершину с самым коротким известным расстоянием и смотрим расстояния от нее. Если мы добавим в очередь одну и ту же вершину и расстояние, то мы просто два раза рассмотрим одни и те же пути из нее - это не имеет смысла.
Аноним 27/05/20 Срд 01:23:25 #153 №221180094 
>>221180057
Логично...
Аноним 27/05/20 Срд 01:24:05 #154 №221180127 
>>221179686
Ну да...
Аноним 27/05/20 Срд 01:32:49 #155 №221180526 
>>221179359
>>221179400
Навскидку - чтобы определить, что элемент в очереди повторился и пропустить его достаточно:
auto u = Q.top();
Аноним 27/05/20 Срд 01:33:35 #156 №221180562 
>>221180526
Q.pop();
if (u.first > d) continue;
Аноним 27/05/20 Срд 01:33:54 #157 №221180578 
>>221180562
Да ебаный в рот
Аноним 27/05/20 Срд 01:34:08 #158 №221180586 
>>221180526
Ну вон же челик написал, что они вообще повторяться не должны, если алгоритм нормально написан...
Аноним 27/05/20 Срд 01:34:17 #159 №221180593 
>>221180578
if (u.first > d[u.second]) continue;
Аноним 27/05/20 Срд 01:35:25 #160 №221180642 
>>221180593
ну дак нормальных кодеров не осталось
Аноним 27/05/20 Срд 01:38:16 #161 №221180760 
>>221180586
При выполнении условия уникальности по ключу в куче да. Обычная std::priority_queue этого не позволяет просто так сделать
Аноним 27/05/20 Срд 01:39:11 #162 №221180809 
>>221180642
У меня просто сообщения отправлялись прежде чем я их допечатывал, поэтому на несколько размазалось
Аноним 27/05/20 Срд 01:43:29 #163 №221181010 
http://2ch.hk/b/res/221179030.html
Аноним 27/05/20 Срд 01:46:31 #164 №221181150 
>>221180760
Да причём тут контейнер... В графе не может быть разных вершин с одинаковым именем и расстоянием до данной, если по какой-то причине мы такую записали, хотя у нас уже есть такая, то алгоритм неправильный...
Аноним 27/05/20 Срд 01:56:57 #165 №221181623 
>>221181150
В графе нет, в очереди может появиться одна и та же вершина с разными расстояниями: рассмотрим ребра 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 уже в очереди и поменять его приоритет. Этого в стандартной приоритетной очереди сделать нельзя.
Аноним 27/05/20 Срд 01:59:34 #166 №221181763 
>>221181623
Ну так алгоритм про обход графа же...
Аноним 27/05/20 Срд 02:00:29 #167 №221181805 
>>221181623
>У нас возникло повторение вершины в очереди.
Не повторение вершины, а повторение пары (вершина, расстояние)...
>В графе не может быть разных вершин с одинаковым именем и расстоянием
Аноним 27/05/20 Срд 02:03:00 #168 №221181920 
>>221181805
Верно. Я уточнял ситуацию, которая возникала в
>>221178877
>>221179155
Там нет дупликации пар, только вершин
Аноним 27/05/20 Срд 02:13:29 #169 №221182402 
>>221181920
Погоди, но приоритет-то это расстояние как раз, там могут быть вершины с разными именами и одинаковыми расстояниями, сет точно не подойдёт.
Аноним 27/05/20 Срд 02:18:34 #170 №221182601 
>>221182402
Приоритет это расстояние в алгоритме. В коде приоритет это пара расстояние/номер вершины. Пара сравнивается сначала по расстоянию, потом по номеру вершины, поэтому приоритетеная очередь и срабатывает. Set сработает точно так же. Ключом выступает пара, а не только расстояние.

Конкретные проблемы читаемости кода, которые и приводят к такому недопониманию я рассмотрел здесь, кстати:
>>221179150
Аноним 27/05/20 Срд 02:19:43 #171 №221182646 
>>221182601
>Ключом выступает пара, а не только расстояние.
Если ключ это пара, то никаких проблем нет, так как одинаковых пар нет.
Аноним 27/05/20 Срд 02:26:58 #172 №221182936 
>>221173385 (OP)
пиши на си сам свой стек хуль тут ебатня какая-то
Аноним 27/05/20 Срд 02:27:40 #173 №221182954 
>>221182646
Именно. Я и пытался показать, что в данном коде нет проблема корректности из-за дупликации, но есть проблема читаемости.
Аноним 27/05/20 Срд 02:28:08 #174 №221182967 
>>221182954
По-моему ты только всех запутал.
Аноним 27/05/20 Срд 02:46:13 #175 №221183751 
>>221178775
Ты давно видел на cppreference полные сорцы той же пары?
То, что они выставляют интерфейс на обозрение понятно, на то он интерфейс.
comments powered by Disqus

Отзывы и предложения