Задача "Флойд-1"
Дан полный (т.е. есть ребра между всеми парами вершин)
ориентированный взвешенный граф.
По его матрице смежности постройте матрицу кратчайших путей
между его вершинами. Гарантируется, что в графе нет циклов
отрицательного веса.
Входные данные:
В первой строке входного файла записано
единственное число: N (1 <= N <= 100) -
количество вершин графа. В следующих N строках по N чисел -
матрица смежности графа (j-ое число в i-ой строке соответствует
весу ребра из вершины i в вершину j). Все числа по модулю
не превышают 100. На главной диагонали матрицы - всегда нули.
Выходные данные:
Выведите N строк по N чисел - матрицу кратчайших расстояний
между парами вершин. j-ое число в i-ой строке должно быть равно
весу кратчайшего пути из вершины i в вершину j.
Пример входного файла
4
0 5 9 100
100 0 2 8
100 100 0 7
4 100 100 0
Пример выходного файла
0 5 7 13
12 0 2 8
11 16 0 7
4 9 11 0
|
