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

Четвертьфинал, Рыбинск, 16 октября 2003

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

D. Cops and Thieves

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
The Galaxy Police (Galaxpol) found out that a notorious gang of thieves has plans for stealing an extremely valuable exhibit from the Earth Planetary Museum — an ancient microprocessor. The police chiefs decided to intercept the criminals on the way from their refuge to the museum. A problem arose while planning the police operation: would it be possible for the Galaxpol staff to control all the possible routes of the criminals?
The galaxy transport system is designed as follows. Each planet has a transport station that is connected to some of the other stations via two-way teleportation channels. Transport stations vary in their sizes, so different numbers of policemen may be required to take control over different stations. In order not to upset the operation, it was decided to leave the planets that are next to the museum or the refuge without any police control.
Help the Galaxpol to place their staff at the stations in order to block all possible routes of the thieves.

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

The first line of the input contains a single integer 1 < K ≤ 10000 — the number of policemen engaged to control the stations.
The second line has four integers: N, M, S and F delimited with white-space character.
N is the number of stations in the galaxy (the stations are numbered from 1 to N); 3 ≤ N ≤ 100.
M is the number of teleportation channels; N − 1 ≤ MN · (N − 1) / 2.
S is the number of the planet (and the station) where the museum is; 1 ≤ SN.
F is the number of the planet (and the station) where the thieves’ refuge is; 1 ≤ FN.
The next line contains N integers (x1, …, xN) separated with white-space character — the number of policemen required to control each of the stations (∑i=1Nxi ≤ 10000).
Then M lines follow that describe the teleportation channels. Each of these lines contains a pair of space-delimited integers — the numbers of stations being connected by a channel. The channel system is designed so that it is possible to reach any station from any other one (probably it would require several channel transitions).

Результат

Write “YES” if it is possible to block all the possible routes within given limitations, and “NO” otherwise.

Примеры

исходные данныерезультат
10
5 5 1 5
1 6 6 11 1
1 2
1 3
2 4
3 4
4 5
NO
10
5 5 1 5
1 4 4 11 1
1 2
1 3
2 4
3 4
4 5
YES
Автор задачи: © Sergey G. Volchenkov, 2003(volchenkov@yandex.ru); Vladimir N. Pinaev, 2003(vpinaev@mail.ru; http://www.pic200x.chat.ru); Michael Y. Kopachev, 2003 (mkopachev@krista.ru).
Источник задачи: 2003-2004 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 15-16, 2003
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1277. Cops and Thieves