№ 5557. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?

Посчитаем число путей, приходящих в каждую вершину. Для каждой вершины это сумма чисел путей, приходящих по входящим в неё дорогам.

От А до Б, В и Г ведёт по одной дороге. Поэтому: Б — 1, В — 1, Г — 1.

В Д можно попасть из Б и В: Д — 1 + 1 = 2. В Е — из В и Д: Е — 1 + 2 = 3. В Ж — из В и Г: Ж — 1 + 1 = 2.

В И можно попасть из Д и Е: И — 2 + 3 = 5. В К — из Ж: К — 2.

В Л ведут дороги из Е, И, Ж и К, поэтому число путей равно 3 + 5 + 2 + 2 = 12.

Ответ: 12 путей.