3. Тип 4 № 43769. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

Рассмотрим пути из A в D, не посещая один пункт повторно. Дороги: AB — 2 км, AC — 4 км, AE — 6 км, BC — 1 км, CD — 5 км, CE — 1 км, DE — 3 км.

1. A → B → C → E → D: 2 + 1 + 1 + 3 = 7 км.
2. A → B → C → D: 2 + 1 + 5 = 8 км.
3. A → C → E → D: 4 + 1 + 3 = 8 км.
4. A → C → D: 4 + 5 = 9 км.

Маршрут A → B → C → E → D не повторяет пункты и короче остальных допустимых путей.

Ответ: 7 км.