Олимпиадный тренинг

Задача . Граф сети


Задача

Темы:
Петя проектирует модель распределенной сетевой инфраструктуры. Инфраструктура может быть представлена в виде графа и состоит из вычислительных узлов, на которых будут размещаться различные сервисы (вершины графа) и сетевых соединений (ребра графа). Граф Пети выглядит следующим образом.


Числа, указанные на узлах – оценка стоимости подключения нового соединения к соответствующему узлу. Стоимость добавления любого нового соединения равна сумме чисел, указанных на соединяемых узлах, независимо от ранее добавленных сетевых подключений. Вася посмотрел проект и сказал, что по требованиям надежности необходимо, чтобы между любыми двумя узлами существовало не меньше двух различных путей, в которых нет одинаковых сетевых соединений. Вася предложил Пете добавить одно или несколько сетевых соединений, чтобы проект стал соответствовать требованиям надежности. Но поскольку Петя экономный, он хочет также сделать это так, чтобы суммарная стоимость добавления всех новых сетевых соединений оказалась минимальной. Определите эту минимальную суммарную стоимость и укажите в ответе как целое число.

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя