олимпиадники-информатики

Разбор задачи на сайте acmp.ru №135
Алгоритм Флойда - алгоритм для нахождения кратчайших расстояний между всеми парами вершин графа. Также применяется для построения матрицы достижимости графа и построения множества истоков и множества стоков.


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

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

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

Решение:
Введем N и матрицу смежности:

int n;
cin >> n;
int d[n][n];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
  cin >> d[i][j];

Реализуем алгоритм Флойда, т. е. найдем кратчайшие расстояния между всеми парами вершин графа.

for (int l = 0; l < n; ++l)
for (int i = 0; i < n; ++i)
  for (int j = 0; j < n; ++j)
   d[i][j] = min(d[i][j], d[i][l] + d[l][j]);

Три вложенных цикла содержат операцию, исполняемую за константное время O(n³), то есть алгоритм имеет кубическую сложность.

Выведем результат, т. е. массив d:

for (int i = 0; i < n; ++i){
    for (int j = 0; j < n; ++j)
	cout << d[i][j] << " ";
    cout << endl;
}

Полный код:

#include <bits/stdc++.h>
 
using namespace std;
 
int32_t main() {
int n;
cin >> n;
int d[n][n];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
  cin >> d[i][j];
for (int l = 0; l < n; ++l)
for (int i = 0; i < n; ++i)
  for (int j = 0; j < n; ++j)
   d[i][j] = min(d[i][j], d[i][l] + d[l][j]);
for (int i = 0; i < n; ++i){
    for (int j = 0; j < n; ++j)
	cout << d[i][j] << " ";
    cout << endl;
}
return 0;
}

Сдать задачу: https://acmp.ru/inde...ask&id_task=135