Реши

Привет! Давай посмотрим, что у нас тут есть.

Тебе нужно определить длину кратчайшего пути между точками A и E, используя только дороги, протяженность которых указана в таблице.

Для начала записываем все прямые пути между A и E, используя данные из таблицы:

• A → E напрямую мы не можем, так как нет прямой дороги;
• A → B → E: 1 + 7 = 8 км;
• A → C → E: мы не можем так поехать напрямую, так как нет прямой дороги между C и E;
• A → D → E: снова нет прямой дороги между D и E;
• и так далее, комбинируем все возможные пути через точки B, C или D.

Теперь нужно рассмотреть пути через один и более промежуточных пунктов, например через В и С:

• A → B → C → E: 1 (A → B) + 2 (B → C) + 3 (C → E) = 6 км.
• A → B → D → E: 1 (A → B) + 2 (B → D) + 4 (D → E) = 7 км.
• A → C → B → E: мы не можем поехать из C в B, так как нет информации о дороге C → B.
• A → C → D → E: мы не можем поехать из C в D напрямую, так как нет информации о дороге C → D.
• и так далее, комбинируем все оставшиеся пути.

Исходя из наших расчетов, самый короткий путь из A в E проходит через точки B и C и