ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Личное первенство УрГУ 2001

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Маршрутизация

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Имеется сеть из нескольких компьютеров, с настроенной по правилам TCP/IP маршрутизацией. Это означает, что:
  1. Каждый компьютер имеет 1 или более сетевых интерфейсов;
  2. Каждый интерфейс идентифицируется IP-адресом и маской подсети — это два 4-х байтных числа, разделённые точками через каждый байт, причём в двоичном представлении маска подсети выглядит следующим образом: сначала идёт k единиц, потом m нулей, k + m = 8*4 = 32. (Например, 212.220.35.77 — IP-адрес, 255.255.255.128 — маска).
  3. 2 компьютера относятся к одной подсети, если (IP1 AND NetMask1) = (IP2 AND NetMask2), где IPi и NetMaski — IP-адрес и маска i-го компьютера, AND — побитовое умножение.
  4. Пакет между компьютерами, находящими в одной подсети передаётся непосредственно.
  5. Пакет между компьютерами, находящимися в 2-х разных подсетях, проходит через компьютеры, имеющие интерфейсы, подключенные к нескольким подсетям, причём при переходе из подсети в подсеть компьютер, на котором осуществляется этот переход, должен иметь интерфейсы, относящиеся к обеим подсетям.
Задача состоит в том, чтобы найти кратчайший путь пакета между двумя указанными компьютерами.

Исходные данные

В первой строке стоит число N — количество компьютеров в сети, далее идёт N секций, описывающих интерфейсы каждого компьютера. В первой строке секции стоит число K — количество интерфейсов этого компьютера, затем следуют K строк с описанием интерфейсов в виде пар IP-адресов и масок. В последней строке стоят номера двух компьютеров, между которыми надо найти путь.
Известно, что 2 ≤ N ≤ 90 и K ≤ 5.

Результат

Если путь существует, выведите «Yes» и в следующей строке через пробел номера компьютеров, через которые проходит путь. Если такого пути не существует, выведите «No».

Пример

исходные данныерезультат
6
2
10.0.0.1 255.0.0.0
192.168.0.1 255.255.255.0
1
10.0.0.2 255.0.0.0
3
192.168.0.2 255.255.255.0
212.220.31.1 255.255.255.0
212.220.35.1 255.255.255.0
1
212.220.31.2 255.255.255.0
2
212.220.35.2 255.255.255.0
195.38.54.65 255.255.255.224
1 
195.38.54.94 255.255.255.224
1 6
Yes
1 3 5 6
Автор задачи: Евгений Кобзев
Источник задачи: Ural State Univerisity Personal Contest Online February'2001 Students Session
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1072. Маршрутизация