Floyd-Warshall's Algorithm.cpp

From Algorithmist
Jump to navigation Jump to search
#include <iostream>
#define SIZE 1000

inline long int MINIMUM__(long int a,long int b)
{
	if(a<b)
		return a;
	return b;
}
bool MATRIX_DIST[SIZE][SIZE];
long int DistARR__[SIZE][SIZE]={0};
long int Dist(long int k,long int i,long int j)
{
        //Implemented By ShahroOz !!
	if(DistARR__[i][j]!=0)
	{
		return DistARR__[i][j];
	}
	if(MATRIX_DIST[i][j]==1)
	{
		DistARR__[i][j]=1;
		return 1;
	}
	if(k<=0)
	{
		return 1000000;
	}
	return DistARR__[i][j]=MINIMUM__(Dist(k-1,i,k-1)+Dist(k-1,k-1,j),Dist(k-1,i,j));
}

int main()
{
	int n;
	std::cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			std::cin>>MATRIX_DIST[i][j];
		}
	}
	std::cout<<Dist(n,0,1);
}