|
Дистанционный практикум по программированию
|
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
210. B - Агенты
|
| Статистика | Послать на проверку | Задачу добавил Неизвестный |
|
Из-за участившихся раскрытий своих агентов, Комитет Государственной Безопасности Бутыляндии решил провести реформу, направленную на улучшение их деятельности. Первым делом необходимо обеспечить безопасность встреч агентов. Ваша программа должна помочь в решении этой проблемы. Вам дано описание путей в Бутыляндии и начальные положения двух агентов. Ваша программа должна ответить, возможно ли безопасная встреча этих агентов. Чтобы быть в безопасности агенты должны соблюдать такие условия: - Агенты двигаются в течение дня, и встречаются вечером, - Агент должен изменять место пребывания каждый день, - Агенты могут путешествовать только по дорогам, соединяющим города (в Бутыляндии, имеются односторонние дороги), - Агент не может двигаться слишком быстро (это может выглядеть очень подозрительным) - в течение одного дня, он не может путешествовать дальше, чем в соседний город, - Расстояние между двумя связанными городами настолько коротко, что агент, отправившись от одного города утром, достигнет другого вечером, - Встречей называется такое состояние, когда два агента находятся в том же самом городе в тот же самый вечер. Задача Ваша программа должна - Читать число городов и описания сети путей в Бутыляндии и стартовые положения агентов из входного файла AGE.IN, - Проверять, возможна ли безопасная встреча, и если так, то, через сколько дней, - Выводит результат в файл AGE.OUT. Входные данные В первой строке файла AGE.IN, имеются два целых числа n и m, разделенные пробелом, где 1 <= n <= 250, 0 <= m <= n * (n-1). Во второй строке даны два целых числа a1 и a2, разделенные пробелом, 1 <= a1, a2 <= n и a1 <> a2. a1 и a2 стартовые положения агентов Номер 1 и Номер 2. В m следующих строк даны пары чисел a и b, разделенные пробелом, 1 <= a, b <= n и a <> b. Эти числа означают, что имеется путь от города a к городу b. Выходные данные: Единственная строка файла AGE.OUT должна содержать: - Одно положительное целое число, которое является минимальным временем (в днях) необходимым, чтобы устроить безопасную встречу двух агентов, если она возможна, - Слово NIE (НЕ в Польском) - если такая встреча не возможна. Пример INPUT: 6 7 1 5 1 2 4 5 2 3 3 4 4 1 5 4 5 6 OUTPUT: 3 |
| Статистика | Послать на проверку | Автор/источник: |
| Задачи с соревнований / | Тренировки ВоГТУ / | Тренировка 07.10.2006 / |
| 210. | 211. C - Простые гири | 212. D - Метро | 213. E - Квадраты |
| время генерации 0.234 сек. | |
| © Copyright ВоГТУ, АВТ, Носов Д.А. |