44. Тип 4 № 18425. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Строки и столбцы таблицы идут в порядке A, B, C, D, E; прочерк означает, что дороги нет: A —, 1, 4, 3, 7; B 1, —, 2, 5, —; C 4, 2, —, 3, —; D 3, 5, 3, —, 2; E 7, —, —, 2, —. Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт C. Передвигаться можно только по дорогам, указанным в таблице, два раза посещать один пункт нельзя.

Нужен простой путь из A в E, который проходит через C, не посещая ни один пункт дважды.

1. Маршрут A—B—C—D—E проходит через C и не повторяет пункты. Его длина: 1 + 2 + 3 + 2 = 8 км.
2. Другой допустимый маршрут A—C—D—E имеет длину 4 + 3 + 2 = 9 км. Маршрут A—C—B—D—E длиннее: 4 + 2 + 5 + 2 = 13 км.
3. Маршрут через C и затем D—E, начинающийся A—D—C, потребовал бы повторно посетить D, поэтому он запрещён.

Ответ: 8 км.