Сколько существует кратчайших маршрутов между пунктами

Решение по шагам

1. 1

   Шаг 1. Два числа на каждый пункт

   Такие задачи решают одним проходом, но храня для каждого пункта $X$ сразу две величины:

   • $d(X)$ — длина кратчайшего пути из А в $X$;
   • $k(X)$ — сколько разных путей имеют эту длину.

   Правило пересчёта при рассмотрении дороги $Y \to X$ длиной $w$: если $d(Y)+w$ меньше текущего $d(X)$ — записываем новое расстояние и $k(X)=k(Y)$; если равно — расстояние не меняем, а счётчик увеличиваем: $k(X) = k(X)+k(Y)$.

2. 2

   Шаг 2. Порядок обработки и первые пункты

   Все дороги ведут «вперёд» по цепочке А, Б, В, Г, Д, Е, поэтому обрабатывать пункты можно просто в этом порядке — к моменту разбора пункта все ведущие в него дороги уже учтены.

   Старт: $d(А)=0$, $k(А)=1$.

   В Б ведёт только дорога из А: $d(Б)=2$ км, $k(Б)=1$.

   В В ведут две дороги: из А это $0+3=3$, из Б это $2+1=3$. Длины равны, поэтому $d(В)=3$ км и $k(В)=1+1=2$.