На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите сумму протяженностей дорог из пункта В в пункт Г и из пункта Г в пункт Б, если известно, что длина дороги ЕЖ меньше, чем длина дороги БГ. В ответе запишите целое число.
Ниже приведён один из вариантов решения задачи.
Будем считать, что в приведённой задаче в силу независимости таблицы (с данными длинами) и схемы (с буквенными обозначениями пунктов) необходимо сопоставить ребрам графа длины так, чтобы условие «длина дороги ЕЖ меньше, чем длина дороги БГ» выполнялось, а при этом маршрут из пункта В в пункт Г и далее из Г в пункт Б имел однозначную протяжённость.
Шаг 1. Анализ структуры
Предположим, что схема содержит ровно те вершины, которые упоминаются в условии: пункты В, Г, Б, а также пункты, участвующие в ребрах ЕЖ и БГ. При этом одинаковость ребра ...