|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 07-1. Флойд - 1
| Имя входного файла | input.txt |
| Имя выходного файла | output.txt |
| Максимальное время работы на одном тесте: | 5 секунд |
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.
Формат входных данных
В первой строке входного файла записано
единственное число N (1 <= N <= 100) -
количество вершин графа. В следующих N строках по N чисел -
матрица смежности графа (j-ое число в i-ой строке соответствует
весу ребра из вершины i в вершину j). Все числа по модулю
не превышают 100. На главной диагонали матрицы - всегда нули.
Формат выходных данных
Выведите N строк по N чисел - матрицу кратчайших расстояний
между парами вершин. j-ое число в i-ой строке должно быть равно
весу кратчайшего пути из вершины i в вершину j.
Пример
| input.txt | output.txt |
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 |