3 задание по огэ (информатика)
Я без понятия как это решать. Мне плохо объяснили или я плохо усвоила. Может вы сможете нормально объяснить как это решать
Поскольку из начальной точки в конечную нет прямого пути, придется делать "пересадки". И полученные расстояния отрезков складывать.
Вариант для примера 1: A-D=6, D-C=5, C-E=4, E-B=7, B-C=2, C-F=2. Итого 6+5+4+7+2+2=26 (максимум для данного примера)
Вариант для примера 2: A-B=2, B-E=5. Итого 2+5=7 (меньше никак, ибо путь до конечной точки минимум 5, а от начальной минимум 2).
Задача решается построением дерева, уже не помню как оно называется, кажется баобаб.
Рисуем кружок, называется узел, обозначаем А. От него проводим ветви к кружкам, обозначенным Б, С, Д, Е, Ф
Над каждой ветвью пишем её вес, то расстояние из таблицы.
Повторяем эту операцию для всех ветвей, выходящих из Б, С, Д, Е ко всем узлам, кроме А, но вес новых ветвей получается как сумма расстояний от А до узла плюс расстояние допустим от А до Б.
Если допустим в узел С можно попасть и из А и из Б и то же справедливо для узла Б, между Б и С делаем две ветви с разным весом. Поскольку нас интересует максимальный по длине путь, то выходя из Б к Ф выбираем для суммы входную ветвь с максимальным весом.