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

Из таблицы видны дороги: A–B — 1 км, A–D — 9 км, A–E — 8 км, B–C — 4 км, B–E — 9 км, C–E — 5 км, D–E — 9 км.

Из C в D можно добраться через E: C–E–D, длина пути равна 5 + 9 = 14 км. Другой допустимый путь — C–B–A–D: 4 + 1 + 9 = 14 км. Путь C–B–A–E–D длиннее: 4 + 1 + 8 + 9 = 22 км.

Ответ: 14 км.