Напишите программу для расчета общих затрат на транспорт во время путешествия Васи. В программе учитывается стоимость

Общие затраты на транспорт

Описание: Для решения этой задачи необходимо написать программу, которая будет рассчитывать общие затраты на транспорт во время путешествия Васи. Входные данные включают количество городов N (от 1 до 1000), которые Вася посетит. Затем следуют N строк, где каждая строка содержит N чисел, разделенных пробелом. Эти числа представляют стоимость переезда между каждой парой городов. Если стоимость переезда равна нулю, это означает, что прямое соединение между городами невозможно.

Для решения задачи можно использовать алгоритм Флойда-Уоршелла. Этот алгоритм помогает найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. В нашем случае, города представляют вершины графа, а стоимость переезда - вес ребра.

Алгоритм Флойда-Уоршелла работает следующим образом:
1. Создать матрицу затрат и заполнить ее данными из входных данных.
2. Для каждой пары городов (i, j) проверить, можно ли добраться из города i в город j напрямую, или через промежуточные города.
3. Если через некоторый город k можно добраться быстрее, то обновить значение затраты до значения через город k.
4. Повторить шаги 2-3 для каждой пары городов (i, j).
5. В результате получим матрицу затрат, в которой на пересечении строки i и столбца j будет указана стоимость самого дешевого пути из города i в город j.

Пример: Вася собирается посетить 4 города. Стоимость переезда между городами задана следующей матрицей:

0 2 3 5

2 0 4 1

3 4 0 2

5 1 2 0

Наша программа должна рассчитать общие затраты на транспорт, которые Вася потратит для посещения всех городов. В этом примере общие затраты будут равны 7.

Совет: Для лучшего понимания алгоритма Флойда-Уоршелла рекомендуется ознакомиться с теорией о поиске кратчайших путей в графе и примерами его использования.

Проверочное упражнение: Напишите программу на языке программирования, которая будет решать данную задачу с использованием алгоритма Флойда-Уоршелла. Входные данные можно представить в виде двумерного массива. Программа должна выводить общие затраты на транспорт.