|
Remote Training on Programming
|
| Hello, Guest! Login or register. |
210. B - Agents
|
| View Problem Statistics | Submit | Problem added Undefined |
|
Из-за участившихся раскрытий своих агентов, Комитет Государственной Безопасности Бутыляндии решил провести реформу, направленную на улучшение их деятельности. Первым делом необходимо обеспечить безопасность встреч агентов. Ваша программа должна помочь в решении этой проблемы. Вам дано описание путей в Бутыляндии и начальные положения двух агентов. Ваша программа должна ответить, возможно ли безопасная встреча этих агентов. Чтобы быть в безопасности агенты должны соблюдать такие условия: - Агенты двигаются в течение дня, и встречаются вечером, - Агент должен изменять место пребывания каждый день, - Агенты могут путешествовать только по дорогам, соединяющим города (в Бутыляндии, имеются односторонние дороги), - Агент не может двигаться слишком быстро (это может выглядеть очень подозрительным) - в течение одного дня, он не может путешествовать дальше, чем в соседний город, - Расстояние между двумя связанными городами настолько коротко, что агент, отправившись от одного города утром, достигнет другого вечером, - Встречей называется такое состояние, когда два агента находятся в том же самом городе в тот же самый вечер. Задача Ваша программа должна - Читать число городов и описания сети путей в Бутыляндии и стартовые положения агентов из входного файла 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 |
| View Problem Statistics | Submit | Author/source: |
| Problems from Contests / | Trainings of Vologda STU / | Training 07.10.2006 / |
| 210. | 211. C - Simple Weights | 212. D - Metro | 213. E - Squares |
| We can all benefit by doing occasional "toy" programs, when artificial restrictions are set up, so that we are forced to push our abilities to the limit. The art of tackling miniproblems with all our energy will sharpen our talents for the real problems. Donald E. Knuth. |
| time generating 0.92 sec. |
| © Copyright VSTU, AVT, Nosov D.A. |