Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1592. Марсианский метрополитен
Поиск в глубину (DFS)Олимпиадные задачи на русском языке
| 04/07/2011 | Лето 2011 - дорешивание (03H) |
| 06/07/2011 | Лето 2011 - 3 (H) |
| 11/07/2016 | Лето 2016 - 7 (E) |
Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Марсианский метрополитен состоит из 13 станций, соединенных `M` туннелями.
Никакой туннель не ведет из станции в нее же и никакая пара станций не может быть соединена
более чем одним туннелем. Для каждого туннеля `i` известно `t_i` – время проезда по нему.
Движение поездов в туннелях двустороннее.
Гусев находится на станции с номером `s`. У него выдалось `T` свободных минут
и он решил прокатиться по станциям метрополитена. При этом, он хочет потратить на все переезды
ровно `T` минут и вернуться на станцию `s`.
Определите, возможно ли это. Если да, то найдите последовательность номеров станций,
которые должен посетить Гусев. Первым и последним числом в последовательности
должен быть номер `s`.
Временем пересадки и ожидания поездов следует пренебречь.
В первой строке входного файла содержатся целые числа `M` `T` `s`.
Далее следует `M` строк с описанием туннелей.
Каждый туннель описывается тремя целыми числами:
двумя номерами станций, `u_i` и `v_i`, и временем `t_i`.
Ограничения: `1\ ≤\ s,\ u_i,\ v_i\ ≤\ 13`; `1\ ≤\ T,\ t_i\ ≤\ 1000`.
В первую строку выходного файла выведите слово "YES", если требуемый маршрут существует,
и "NO" в противном случае.
Если ответ существует, то в следующей строке выведите искомый маршрут.
Если ответов несколько, выведите любой из них.
Пример ввода
4 6 1 1 2 1 2 3 2 3 4 3 4 1 4
Пример вывода
YES 1 2 3 2 1
