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

Из C можно попасть только в A, поэтому маршрут начинается C—A. Далее возможны простые пути к B:

• C—A—B: стоимость 5 + 2 = 7;
• C—A—E—D—B: стоимость 5 + 6 + 1 + 3 = 15.

Других путей без повторного посещения пунктов нет.

Ответ: максимальная стоимость — 15; маршрут C—A—E—D—B.