Решение задачи №135 «Алгоритм Флойда» с ACMP
Условие задачи
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.
Входные данные
В первой строке входного файла INPUT.TXT записано единственное число N (1 ≤ N ≤ 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы - всегда нули.
Выходные данные
В выходной файл OUTPUT.TXT выведите N строк по N чисел - матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно быть равно весу кратчайшего пути из вершины i в вершину j.
Решение на C++
#include<iostream>
using namespace std;
int main(){
int n,i,j,k;
cin>>n;
int a[n][n];
for(i=0;i<n;++i)
for(j=0;j<n;++j)
cin>>a[i][j];
for(k=0;k<n;++k)
for(i=0;i<n;++i)
for(j=0;j<n;++j)
if(a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];
for(i=0;i<n;++i){
for(j=0;j<n;++j)cout<<a[i][j]<<' ';
cout<<endl;}
return 0;}
Условия задач взяты с сайта acmp.ru