Содержание
Вариант 4.5. Кратчайшие маршруты
Все варианты на «Хорошо» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Хорошо.
Постановка задачи
Пункты — вершины транспортной сети, 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.5, 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.5, 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.5, 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.5, created by Ivan Ivanov. OK OK Error: RANGE Error: NOT_FOUND ITEMS 2 0 0 1 4
