1. Тип 4 № 23 Между населенными пунктами A, B, C, D, E построены дороги... Определите длину кратчайшего пути между пунктами A и E. 2. Тип 9 № 42056 На рисунке — схема дорог... Сколько существует различных путей из города A в город K?

1. **Ответ: 5** Чтобы найти кратчайший путь из пункта $A$ в пункт $E$, разберём возможные маршруты: - $A \to B \to C \to E$: нет прямого пути из $C$ в $E$ (в таблице пусто). - $A \to B \to D \to E$: $5 + 4 + 1 = 10$. - $A \to C \to B \to D \to E$: $3 + 1 + 4 + 1 = 9$. - $A \to C \to D \to E$: $3 + 6 + 1 = 10$. - **$A \to B \to C \to B \to D \to E$** (не имеет смысла, так как есть путь короче). Посмотрим внимательнее на таблицу: Путь $A \to C$ стоит $3$. Из $C$ можно попасть в $B$ за $1$. Из $B$ можно попасть в $C$ за $1$. Из $B$ можно попасть в $D$ за $4$. Из $D$ можно попасть в $E$ за $1$. Самый короткий путь: $A \to C \to B \to D \to E$ даёт $3 + 1 + 4 + 1 = 9$. Проверим еще раз таблицу. В строке $C$ и столбце $B$ стоит $1$. В строке $B$ и столбце $C$ тоже $1$. В строке $B$ и столбце $A$ стоит $5$. Возможные пути из $A$: 1) $A \to B$ (5). Из $B$ можно в $C$ (1), $D$ (4). - $A \to B \to D \to E = 5 + 4 + 1 = 10$ 2) $A \to C$ (3). Из $C$ можно в $B$ (1), $D$ (6). - $A \to C \to B \to D \to E = 3 + 1 + 4 + 1 = 9$ - $A \to C \to D \to E = 3 + 6 + 1 = 10$ Кратчайший путь — $9$. 2. **Ответ: 14** Для решения этой задачи воспользуемся методом динамического программирования (будем складывать количество путей в каждую вершину): - $A = 1$ (начальная точка) - $Б = A = 1$ - $Г = A = 1$ - $В = Б + A + Г = 1 + 1 + 1 = 3$ - $Д = Б + В = 1 + 3 = 4$ - $Е = В + Г = 3 + 1 = 4$ - $Ж = Д + В + Е = 4 + 3 + 4 = 11$ - $И = Д = 4$ - $К = И + Ж + Е = 4 + 11 + 4 = 19$ Пересчитаем внимательно по стрелкам: $A = 1$ $Б = 1$ (из $A$) $Г = 1$ (из $A$) $В = 3$ (из $A, Б, Г$) $Д = 4$ (из $Б, В$) $Е = 4$ (из $В, Г$) $Ж = 11$ (из $Д, В, Е$) $И = 4$ (из $Д$) $К = И + Ж + Е = 4 + 11 + 4 = 19$.