ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Отборочный турнир сезона «Зима — 2020» > задача:


J. Макс и выбор такси: такси наносит ответный удар

Отборочный турнир сезона «Зима — 2020»

Старт: 01.фев.2020 в 14:00:00
Финиш: 09.фев.2020 в 23:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (4)

Задачи турнира

• B. Макс и телефонный тариф
• C. Макс и добыча алмазов
• D. Макс и игра с монетами
• E. Макс и пропущенные звонки
• F. Макс и покупка флешек
• G. Макс и рехост стримов
• H. Макс и лестница с цифрами
• I. Макс и новогодние подарки — 2
• J. Макс и выбор такси: такси н...

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 4000/4000/4000/4000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и выбор такси: такси наносит ответный удар
Макс и выбор такси: такси наносит ответный удар
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Как вы помните, Макс и другие студенты, находясь в командировке, часто пользуются услугами такси. На этот раз ребята отправились в другой соседний регион, где проводится знаменитый Апрельский Чемпионат.

Университет-организатор Апрельского Чемпионата имеет N корпусов, пронумерованных от 1 до N. Корпуса соединены сетью из M дорог, проезд по i-й из которых занимает Ti минут.

Макс и его друзья поселились в гостинице, находящейся в непосредственной близости от корпуса, имеющего номер S. К сожалению, никто из ребят не запомнил, в каком именно корпусе будет проходить чемпионат, поэтому сейчас они изучают карту города и планируют, как лучше всего добраться до того или иного корпуса.

Оказалось, что в городе, в котором проводится Апрельский Чемпионат, службы такси имеют ряд особенностей:

  • Во-первых, этих служб очень много (можно считать, что сколь угодно большая группа пассажиров всегда сможет заказать такси).
  • Во-вторых, несмотря на большое количество служб, в каждой из них можно заказать только одну машину.
  • В-третьих, водители разных служб такси не очень жалуют друг друга, и поэтому обязательно поедут к месту назначения различными путями (пути A и B считаются различными, если существует хотя бы одна дорога, входящая в путь A и не входящая в путь B или наоборот).

Макс и другие студенты долго чесали в затылках, силясь понять бесконечную мудрость местной сферы транспортного обслуживания.

Сейчас ребята хотят выяснить, сколько существует корпусов, до которых они могут добраться одновременно и за минимально возможное время, если воспользуются местными службами такси и начнут поездку одновременно. Помогите им найти ответ на этот вопрос. Помните, что во всех такси 4 места для пассажиров.

Входные данные

Первая строка содержит целые числа N и M (1 ≤ N, M ≤ 105, 0 ≤ M ≤ 105) — соответственно количество корпусов университета и соединяющих их дорог.

Следующие M строк описывают дороги. Каждая из них содержит целые числа Ai, Bi и Ti (1 ≤ Ai, Bi ≤ N, 1 ≤ Ti ≤ 105) — соответственно номера корпусов, которые соединяет дорога, и время проезда по ней в минутах.

Следующая строка содержит целые числа S и K (1 ≤ S ≤ N, 1 ≤ K ≤ 1000) — соответственно номер корпуса, рядом с которым расположена гостиница, и количество студентов.

Выходные данные

Выведите одно или более целых чисел — номера корпусов, до которых все студенты, стартовав одновременно, могут доехать также одновременно и за минимально возможное время. Номера следует выводить в порядке возрастания.

Примеры

Входные данные
4 5
1 2 1
1 3 1
2 4 1
3 4 1
2 3 2
1 8
Выходные данные
1 4 
Входные данные
5 7
1 2 1
1 3 2
1 4 3
1 5 4
2 3 1
3 4 1
4 5 1
1 10
Выходные данные
1 4 5 

Для отправки решений необходимо выполнить вход.

www.contester.ru