Такой вопрос. Интернет-провайдер хочет проложить новую сеть. В стране 7 городов, которые нужно соединить между собой так, чтобы из каждого города можно было посылать сообщение в любой другой (возможно, через другие города). Для прокладывания оптоволоконной линии между двумя городами требуется потратить некоторое количество денег. Стоимость прокладки сети между двумя городами записана на линии, соединяющей эти города.



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

Ответ запишите числом без дополнительных пробелов и символов до и после (например: 10).

Для решения задачи минимального остовного дерева можно использовать алгоритм Прима или Краскала. Результаты будут зависеть от конкретных стоимостей прокладки сети между каждой парой городов.