====== Вариант 4.14. Маршруты доставки между складами ======
[[: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.14, 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.14, 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.14, 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.14, created by Ivan Ivanov.
OK
OK
Error: RANGE
Error: NOT_FOUND
ITEMS 2
0 0
1 4