Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Тяжелая доля гастарбайтеров
Как известно, в поисках работы все средства хороши. Иноземец Мусса решил попробовать свои силы в строительных и отделочных работах. Известно, что в стране, в которой Мусса решил подзаработать имеется C городов. Города, в свою очередь, соединены P однонаправленными дорогами. В каждом городе можно заработать D долларов США по курсу национального банка страны, в которую приехал наш герой. После того, как гость отработает в одном городе, он может перебраться в любой другой по дорогам и заработать там. Перемещения абсолютно бесплатны. Можно возвращаться в любой город неограниченное число раз. Мусса попал в такую страну, где очень на высоком уровне развито авиасообщение между городами, но оно, увы, не бесплатно. Имеется F авиамаршрутов, каждый из которых обеспечивает односторонний перелет между двумя городами. Стоимость авиаперелета составляет Ti долларов США. Причем платить за авиаперелет возможно в счет будущих заработков (т.е. иметь нужную сумму в момент перелета необязательно). Начинает свою карьеру в строительном бизнесе наш герой в городе номер S. Путешествовать Мусса может сколько угодно времени (в том числе и бесконечно). Какое максимальное число долларов США может заработать Мусса в данной стране?
Входные данные:
Первая строка входного файла содержит 5 целых чисел: D (1 ≤ D ≤ 1000), P (1 ≤ P ≤ 150), C (2 ≤ C ≤ 220), F (1 ≤ F ≤ 350), S (1 ≤ S ≤ C). 
 Далее содержится P строк, описывающих дороги между городами. Каждая из дорог представляет собой пару целых чисел Ai и Bi (1 ≤ Ai, Bi ≤ C, 1≤ i ≤ P). Затем следует F строк с описанием авиамаршрутов. Каждый из авиамаршрутов представляет собой тройку целых чисел Ji, Ki, Ti (1 ≤ Ji, Ki ≤ C, 1≤ Ti ≤ 50000, 1≤ i ≤ F).

Пример:
В этой стране 5 городов, три дороги и два самолетных рейса. Мусса начинает в городе 1, и может заработать не более 100 долларов в каждом городе за один раз.
Выходные данные:
В выходной файл требуется единственное число – максимальное количество долларов, которое сможет заработать Мусса в этой щедрой стране. Если Мусса может зарабатывать бесконечное число долларов, то выведите число -1.

Пример:
Мусса может перебраться из города 1 в город 5, оттуда в город 2, оттуда в город 3 и всего заработать 4*100 - 150 = 250 долларов.

Примеры:
input.txt output.txt
1 100 3 5 2 1
1 2
2 3
1 5
5 2 150
2 5 120
250

Сложность задачи: 30%



Проверку могут осуществлять только зарегистрированные пользователи!


Показать обсуждение


На сайте гостей 25, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]