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

Нужно найти путь из A в E, посетив каждый пункт ровно один раз. По таблице дороги A–B, A–C, A–E, B–D, B–E, C–D, C–E и D–E имеют длины 1, 1, 4, 3, 3, 2, 1 и 5 соответственно.

Путь A–B–D–C–E невозможен: между B и D дорога есть, но затем D–C и C–E тоже есть; его длина равна 1 + 3 + 2 + 1 = 7.

Другой допустимый порядок пунктов — A–C–D–B–E — даёт длину 1 + 2 + 3 + 3 = 9. Путь A–B–C–D–E невозможен, поскольку дороги B–C нет; путь A–C–B–D–E невозможен по той же причине.

Ответ: 7.