Задание 1. В Москве между пунктами A, B, C, D, E, F расположены туристические маршруты, протяжённость которых приведена в таблице. Пункт C нужно посетить обязательно. Укажите кратчайший путь между пунктами A и F, учитывая обязательное посещение пункта C. Длины маршрутов: AB = 1, AC = 5, AD = 3, AF = 8, BC = 3, BD = 6, BE = 7, CE = 3, CF = 1, DE = 4, DF = 2; пустые ячейки означают, что маршрута нет. Варианты: ABCF, ADCF, ACDF.

Сначала найдём кратчайший путь из A в C. Напрямую он равен 5, а через B: 1 + 3 = 4. Значит, кратчайший путь — A–B–C.

Из C в F есть прямой маршрут длиной 1, он короче обходных путей.

Объединяем участки: A–B–C–F. Его общая длина равна 1 + 3 + 1 = 5.

Ответ: ABCF.