Задача TouristVasya
Предисловие жюри
Мы предлагаем вам решить известную задачу. Возможно, кто-то из вас имел возможность уже получить ее полный балл. (https://www.e-olymp.com/uk/problems/122)
Жюри это не пугает, а наоборот, именно этот факт был решающий при подготовке заданий. Более того, у вас есть возможность проверять свои решения перед отправкой на официальную проверку неограниченное количество раз в расширенном (правда, не до 100%) наборе тестов, которые подготовило жюри. Мы искренне желаем вам успехов!
Горный туристический комплекс состоит из n турбаз, соединенных между собой m горными переходами (другие маршруты в горах опасны). Каждый переход между двумя базами занимает 1 день. Туристическая группа находится на базе a и собирается попасть на базу b не более чем за d дней. Сколько существует различных таких маршрутов (без циклов) от a до b?
Технические условия. Программа TouristVasya читает с устройства стандартного ввода в одной строке через пробелы пять натуральных чисел n, m, a, b, d (2≤n≤23, 1≤m≤n2, 1≤a≤n, 1≤b≤n, a≠b, 1≤d≤min(8,n–1)), а далее в той же строке m пар чисел u, v (1≤u≤n, 1≤v≤n), где каждая пара описывает существование однодневного перехода, который начинается в u и заканчивается в v. Все пары u, v гарантированно разные. Программа выводит на устройство стандартного вывода одно число — количество маршрутов (без циклов, то есть без повторений турбаз), которые начинаются в a, заканчиваются в b и содержат не более d переходов.
Пример
|
Ввод |
Вывод |
|
|
5 8 2 5 3 1 2 1 3 1 5 2 1 2 4 3 4 3 5 4 1 |
3 |
Тремя маршрутами, которые соответствуют всем требованиям, являются:
(1) 2→1→5; (2) 2→1→3→5; (3) 2→4→1→5.