Как в ЕГЭ · 13 из 20
№23. Сколько путей через город
По мотивам задания №23 (в 2027 году оно про графы: подсчёт путей и оптимальный путь в ориентированном графе без циклов). Схема дорог между городами — все дороги односторонние, по кругу не проехать. Сколько разных путей из одного города в другой проходят через заданные города? На маленькой схеме пути считают «по слоям»; на схеме из тысяч дорог — только с запоминанием.
Что сделать
Посчитайте пути по односторонним дорогам из start в finish, которые проходят через все города из cherez.
Что приходит
rebra— дороги: пары(откуда, куда), города — строкиstartиfinish— откуда и кудаcherez— города, через которые путь обязан пройти, в любом порядке (список, бывает пустым)
Что вернуть
Число путей — целое, бывает очень большим.
Допишите функцию puti в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
Дороги А→Б, А→В, Б→В, Б→Г, В→Г. Путей из А в Г три: А→Б→Г, А→Б→В→Г, А→В→Г. Через В проходят два из них — ответ 2.
puti([("А", "Б"), ("А", "В"), ("Б", "В"), ("Б", "Г"), ("В", "Г")], "А", "Г", ["В"])
2
Граф ориентированный и без циклов: вернуться в город, где уже был, нельзя никаким путём. Две дороги между одной парой городов не встречаются. Путь — последовательность дорог от start до finish; он проходит через город, если город на нём есть. В cherez — до трёх городов, записаны в любом порядке; start и finish в нём не бывают. Путей из города в него самого — один, пустой.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.