e-olymp 974. Флойд-1

Задача

Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Входные данные

В первой строке записано количество вершин графа n (1n100). В следующих n строках записано по n чисел — матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

Выходные данные

Выведите n строк по n чисел — матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.

Тесты

# Входные данные Выходные данные
1 2
0 0
0 0
0 0
0 0
2 4
1 2 0 0
2 2 4 4
0 0 1 1
3 4 2 1
1 0 0 0
2 2 2 2
0 0 1 0
2 2 2 1
3 2
3 2
1 1
3 2
1 1

Код программы:

Решение

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

Ссылки

Условие задачи на e-olymp.com.

Код решения на ideone.com.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *