В Байтландии N городов и M дорог с односторонним движением, соединяющих эти города

Условия
В Байтландии N городов и M дорог с односторонним движением, соединяющих эти города.

При этом выполняется следующие свойства:
Из города с номером 1 можно проехать во все города.
Изо всех городов можно проехать в город с номером N.
Стартовав из какого-либо города, невозможно вернуться назад в тот же город.
Каждая дорога имеет длину 1.


Для каждого города требуется подсчитать сумму длин всех путей через этот город, ведущих
из города 1 в город N.
Система оценки
В задаче 25 тестов (кроме примера). Каждый тест оценивается в 4 балла. Гарантируется,
что не менее чем в 40% тестов N ≤ 10.


Формат входных данных
Первая строка входного файла содержит два целых числа N и M — количество городов и количество дорог соответственно (1 ≤ N ≤ 50; N − 1 ≤ M ≤ N (N − 1)/2. Каждая из последующих M строк содержит по два целых числа ai и bi — начальный и конечный пункты очередной дороги (1 ≤ ai,bi ≤ N; ai ≠ bi).


Формат выходных данных
Для каждого города в порядке их нумерации выведите в новой строке одно целое число – сумму длин всех путей из 1 в N, проходящих через этот город.

Входные данные:
3 3
1 2
2 3
1 3
Выходные данные:
3
2
3

0

Элементарная же задача. В чем проблема?
Вы понимаете как устроен данный граф?

0

Если честно то не совсем

0

0

А с динамическим программированием знакомы?
Задачи о маршрутах в прямоугольнике?

0

Честно,я тоже нет

0

главное про setrecursionlimit не забыть

0

Только как это поможет,если кода нет

0

Сообщение от KesX Только как это поможет,если кода нет

это поможет прочитать и изучить данные темы и попробовать написать свой код

0

Сообщение от KesX Честно,я тоже нет

Понятно. Тогда алгоритм такой.
Допустим нам надо найти сумму всех длин путей из А в В. Пусть в В можно прийти по указанным дорогам из В1, В2, ...
Тогда искомая величина - сумма всех длин путей из А в В1 плюс сумма всех длин путей из А в В2 и так далее. Плюс добавить сумму длин дорог из В1, В2, ... в B.
Соответственно свели задачу к аналогичной, только точки стали чуток поближе.
Суть понятна? Делаете рекурсию с кэшированием значений, может чего и получится.

0