Задача TouristVasya
Передмова журi
Ми пропонуємо вам розв’язати відому задачу. Можливо, хтось із вас мав нагоду вже отримати за неї повний бал. (https://www.e-olymp.com/uk/problems/122)
Журі це не лякає, а навпаки, саме цей факт був вирішальним при підготовці завдань. Навіть більше, у вас є можливість перевіряти свої розв’язки перед відправкою на офіційну перевірку необмежену кількість разів на розширеному (правда, не до 100%) наборі тестів, що їх підготувало журі. Ми щиро бажаємо вам успіхів!
Гірський туристичний комплекс складається з n турбаз, з’єднаних між cобою 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.