Решение задачи №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