Инструменты пользователя

Инструменты сайта


courses:algorithms_structures:cw_2026:grade4:5

Вариант 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
courses/algorithms_structures/cw_2026/grade4/5.txt · Последнее изменение: — 127.0.0.1