|
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
|
||||||
Ошибка "Segmentation fault" при вызове метода erase() контейнера vector05.02.2019, 16:28. Показов 3570. Ответов 34
Метки stl контейнер (Все метки)
Хочу убрать изолированные вершины в графе. На строке 75 выдает "Segmentation fault".
5 4 1 2 5 1 2 3 2 3 4 1 4 10 Выводит: 0: 3 1 1: 2 0 2: 1 3: 0 4: Segmentation fault Метод empty() нормально определяет, что вершина с номером 4 изолирована, но удалить её не получается.
0
|
||||||
| 05.02.2019, 16:28 | |
|
Ответы с готовыми решениями:
34
Segmentation fault при вызове метода Segmentation fault при вызове std::vector::insert libcUrl: segmentation fault при вызове метода curl_easy_init() |
|
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
|
|
| 05.02.2019, 16:43 | |
|
А само задание какое? Что в коде происходит?
0
|
|
|
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
|
||||||
| 05.02.2019, 17:16 [ТС] | ||||||
|
Задание вот https://codeforces.com/problem... ?locale=ru
Пробовал решить представляя граф матрицей смежности, но граф занимал лимит памяти на большом числе вершин. Теперь вот решил использовать список смежности, чтобы память сэкономить Из решения задачки я вытащил кусок кода Сначала в строках 15-56 я считываю граф и заношу его в вектор однонаправленных списков, эта часть кода правильна (но возможно не эффективна) В строках 58-66 в первый раз вывожу граф на экран В строках 68-78 избавляюсь от изолированных вершин (если в векторе есть пустой список, то этот элемент вектора следует удалить) В строках 80-88 второй раз вывожу граф на экран Меня интересует вот этот кусочек кода, строки 68-78
Добавлено через 3 минуты Хочу задачку с использованием STL решить, нужно же все таки начинать пользоваться благами, которые C++ предоставляет Добавлено через 44 секунды Думаю, что итератор неправильно сдвигаю Добавлено через 1 минуту Саму задачку решаю алгоритмом Дейкстры
0
|
||||||
|
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
|
|
| 05.02.2019, 17:29 | |
|
peoplep8, интересная задача, а как именно вы Дейкстрой решаете? Он вроде находит кратчайшее расстояние между двумя вершинами? И если для каждого города в котором нету склада вызывать алгоритм и конечной вершиной выбирать все города в которых склад есть - я думаю оно по времени не пройдет
Добавлено через 16 секунд peoplep8, или вы как-то по другому делаете?
0
|
|
|
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
|
||||||
| 05.02.2019, 17:29 [ТС] | ||||||
|
Пробовал вот так, но даже в цикл не заходит
0
|
||||||
|
Mental handicap
1246 / 624 / 171
Регистрация: 24.11.2015
Сообщений: 2,429
|
||||
| 05.02.2019, 17:29 | ||||
auto в приоритете.
1
|
||||
|
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
|
|
| 05.02.2019, 17:32 | |
|
peoplep8, Хотя вообще, я думаю это задание именно на алгоритм Флойда-Уоршелла
![]() Хотя я могу и ошибаться, пройдет ли n^3 для 10^5?
1
|
|
|
Mental handicap
1246 / 624 / 171
Регистрация: 24.11.2015
Сообщений: 2,429
|
|||
| 05.02.2019, 17:32 | |||
|
1
|
|||
|
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
|
|
| 05.02.2019, 17:43 [ТС] | |
|
Дейкстра находит кратчайшие расстояния от одной начальной вершины до всех остальных.
Я делаю так: для каждого склада с мукой нахожу путь до всех остальных вершин потом в массиве weights (он содержит пути до всех остальных вершин) исключаю расстояния до складов с мукой (мне не нужно знать расстояние от одного склада с мукой для другого) нахожу минимальный элемен min в weights заношу min в массив минимальных расстояний mins для каждого склада выбираю минимальный элемент из mins - это и будет минимальная сумма которую должна Маша заплатить Добавлено через 7 минут Azazel-San, если i-й список в векторе g пуст, то я сдвигаю итератор на i и удаляю этот список. Функция advance же сдвигает итератор...
0
|
|
|
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
|
|
| 05.02.2019, 17:48 | |
|
peoplep8, Можно вопрос пожалуйста?
Допустим вы посчитали расстояния для всех складов с мукой ( k* асимптотику Дейкстры(n^2 + m, m можно опустить) т.е у вас n^3 в худшем случае) ,потом вам необходимо я полагаю n^2 * k операций для того,чтобы исключить все склады с мукой из ответов. Зачем же вам удалять изолированные вершины в конце? Если можно на этапе исключения складов с мукой выбрать минимальное растояние? Ну и n^3 вы уверены что будет работать для 2 сек и n = 10^5 ?
0
|
|
|
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
|
|
| 05.02.2019, 17:49 [ТС] | |
|
LegionK, возможно, что Флойдом — Уоршеллом проще решить, но Дейкстрой у меня работал для n = 450; m = 20; k = 163; но на n= 10000; m = 5054; k = 3791 получалось MEMORY_LIMIT_EXCEEDED. Я все таки хочу попробовать отослать решение с Дейкстрой. но представляя граф списком смежности, а потом уже разберусь Флойдом — Уоршеллом
0
|
|
|
Mental handicap
1246 / 624 / 171
Регистрация: 24.11.2015
Сообщений: 2,429
|
|
| 05.02.2019, 17:50 | |
|
0
|
|
|
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
|
|
| 05.02.2019, 17:50 | |
|
peoplep8, нет,нет, вы неправильно меня поняли, Флойд_Уоршелл имеет такую же асимптотику, т.е n^3
Я намекнул,что возможно там немного другое решение? Но главная мысль была о том,зачем же вам в конце удалять изолированные вершины?
0
|
|
|
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
|
|||||||||||
| 05.02.2019, 17:57 [ТС] | |||||||||||
|
Azazel-San, я до этого скидывал этот код
Добавлено через 58 секунд LegionK, я их удаляю не в конце, а в начале, перед работой Дейкстры Добавлено через 1 минуту LegionK, Потому что с изолированными вершинами алгоритм Дейкстры путается (вроде входит в бесконечный цикл) Добавлено через 2 минуты Вот код полностью, если интересно
0
|
|||||||||||
|
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
|
|
| 05.02.2019, 17:57 | |
|
peoplep8, дико извиняюсь, но полагаю,что после строки 68 идет только вывод вашего графа (возможно проверка корректности удаления вершин), но ,извиняюсь за нескомный вопрос, зачем же вам удалять вершины из графа? Если вершина изолированна путь в неё так и не будет найден, а асимптотику это не улучшит и не ухудшит в среднем случае. Нет,конечно, есть случаи когда это повлияет в лучшую сторону, но может быть и наоборот.
0
|
|
|
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
|
|
| 05.02.2019, 18:01 [ТС] | |
|
А все-таки, как же правильно удалить вершину из списка смежности графа средствами STL?
0
|
|
|
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
|
|
| 05.02.2019, 18:03 | |
|
peoplep8, нет,конечно это замечательно, но,вы,наверное не прочитали разбор задания,верно? Конечно,это практика решения задач,это хорошо и замечательно, но там имеется более красивое решение, которое почти не требовательно к памяти и времени выполнения
![]() Так что,если возможно,ваш код, как я предполагаю, не пройдет ряд тестов из-за большой временной сложности, советую посидеть за чашкой чая и подумать над парой моментов в этой задаче, а флойдов и дийкстр оставить на потом)
0
|
|
|
Mental handicap
1246 / 624 / 171
Регистрация: 24.11.2015
Сообщений: 2,429
|
|
| 05.02.2019, 18:03 | |
|
0
|
|
|
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
|
|
| 05.02.2019, 18:04 [ТС] | |
|
LegionK, да, возможно их и не нужно удалять
0
|
|
|
Mental handicap
1246 / 624 / 171
Регистрация: 24.11.2015
Сообщений: 2,429
|
||
| 05.02.2019, 18:05 | ||
|
0
|
||
| 05.02.2019, 18:05 | |
|
Помогаю со студенческими работами здесь
20
Ошибка Segmentation fault при вызове glGenBuffers() Segmentation fault при вызове функции Segmentation fault при вызове malloc Segmentation fault при использовании метода show()
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога
Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
|
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога
Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
|
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога
Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
|
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
|
|
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога
В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
|
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога
Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
|
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога
Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
|
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
|