====== Вариант 4.15. Задержки в сети передачи данных ====== [[:courses:algorithms_structures:cw_2026:grade4:start|Все варианты на «Хорошо»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]] Уровень: **Хорошо**. ===== Постановка задачи ===== Пункты — узлы сети, w — задержка направленного соединения. Нужно находить минимальные суммарные задержки из выбранного узла. Разработайте систему поиска минимальной суммарной стоимости маршрутов в направленной сети. Из выбранного пункта нужно получить расстояния до всех пунктов, включая информацию о недостижимых. Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат. ===== Данные и начальное состояние ===== * ''n'' — число пунктов от 1 до 100000; их номера от 0 до n−1. * ''u'', ''v'', ''s'' — номера пунктов; ''w'' — целая стоимость от 0 до 1000000000. * Одновременно не более 200000 направленных соединений. До INIT сеть не инициализирована. ===== Операции ===== ^ Команда ^ Действие ^ Ответ ^ | ''INIT n'' | Создать сеть из n пунктов без соединений, удалив прежние данные. | OK | | ''EDGE u v w'' | Добавить направленное соединение u→v; если оно уже есть, заменить стоимость. | OK | | ''DEL u v'' | Удалить направленное соединение u→v. | OK; если его нет, Error: NOT_FOUND | | ''DIST s'' | Получить минимальные суммарные стоимости из s до каждого пункта. | ITEMS n, затем n строк v distance по возрастанию v; недостижимое расстояние обозначить INF | ===== Правила выполнения и ошибки ===== Соединение u→v не создаёт v→u. Соединения пункта с самим собой и нулевая стоимость разрешены; нескольких соединений одной направленной пары нет. Расстояние из s в s равно 0. Сначала проверяются синтаксис и статические диапазоны, затем наличие INIT (при его отсутствии STATE), затем принадлежность номеров диапазону [0,n) (иначе RANGE). Отрицательная стоимость даёт RANGE ещё до проверки инициализации. Каждый DIST учитывает текущую сеть; конкретные маршруты не выводятся. Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы. ===== Требования к эффективности ===== Пусть m — текущее число направленных соединений. INIT — O(n); EDGE и DEL — не хуже O(d(u)+1), где d(u) — число исходящих соединений u. DIST — не хуже O((n+m)·log(n+m+2)), память — O(n+m). Метод поиска маршрутов студент выбирает и обосновывает самостоятельно. В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях. ===== Формат ввода и вывода ===== Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта: Course work for option 4.15, created by Ivan Ivanov. Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием. ===== Примеры ===== ==== Пример 1. Несколько маршрутов и недостижимый пункт ==== Ввод: 1 5 INIT 4 EDGE 0 1 4 EDGE 0 2 10 EDGE 1 2 3 DIST 0 Вывод: Course work for option 4.15, created by Ivan Ivanov. OK OK OK OK ITEMS 4 0 0 1 4 2 7 3 INF ==== Пример 2. Замена стоимости и направление ==== Ввод: 1 5 INIT 2 EDGE 0 1 5 EDGE 0 1 0 DIST 0 DIST 1 Вывод: Course work for option 4.15, created by Ivan Ivanov. OK OK OK ITEMS 2 0 0 1 0 ITEMS 2 0 INF 1 0 ==== Пример 3. Неверная стоимость не меняет соединение ==== Ввод: 1 5 INIT 2 EDGE 0 1 4 EDGE 0 1 -1 DEL 1 0 DIST 0 Вывод: Course work for option 4.15, created by Ivan Ivanov. OK OK Error: RANGE Error: NOT_FOUND ITEMS 2 0 0 1 4