//Author Antonio-Gabriel Sturzu

#include<mpi.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define lim 100001

int main(int argc,char *argv[])
{
	int **m,n,i,j,k,rc,numtasks,rank,dim,next,strip,*line,root,rap;
	MPI_Status status;
	double time1,time2;
	
	//MPI Initialization
	rc = MPI_Init(&argc,&argv);
	if (rc != MPI_SUCCESS) 
	{
		printf ("Error starting MPI program. Terminating.\n");
		MPI_Abort(MPI_COMM_WORLD, rc);
	}
	MPI_Comm_size(MPI_COMM_WORLD,&numtasks);
	MPI_Comm_rank(MPI_COMM_WORLD,&rank);
	
	//Reading from file is done by process 0
	if(rank==0)
	{	
		FILE *f=fopen("royfloyd.in","r");
		fscanf(f,"%i",&n);
		m=(int **) calloc(n*n,sizeof(int *));
		for(i=0;i<n;i++)
			m[i]=(int *) calloc(n,sizeof(int));
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
			{
				fscanf(f,"%i",&m[i][j]);
				if(i!=j && m[i][j]==0)
					m[i][j]=lim;
			}
		fclose(f);
	}		

	//Send n's value to all processes
	MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);
	line=(int *) calloc(n,sizeof(int));
	dim=n/numtasks;
	if(rank==numtasks-1 && n%numtasks!=0)
		dim=n-dim*(numtasks-1);
	
	if(rank>0)
	{
		m=(int **) calloc(dim*n,sizeof(int *));
		for(i=0;i<dim;i++)
			m[i]=(int *) calloc(n,sizeof(int));
	}	
	MPI_Barrier(MPI_COMM_WORLD);

	//Send matrix portions to all processes
	if(rank==0)
	{
		next = dim;
		for(k=1;k<numtasks-1;k++) 
		{
			for (i=0;i<dim;i++) 
				MPI_Send(m[next+i],n,MPI_INT,k,1,MPI_COMM_WORLD);
			next+=dim;
		}
		if(numtasks>1)
		{
			if(n%numtasks!=0)
				strip=n-dim*(numtasks-1);
			else
				strip=dim;
			for(i=0;i<strip;i++)
				MPI_Send(m[next+i],n,MPI_INT,numtasks-1,1,MPI_COMM_WORLD);
		}	
	}

	//Receive lines
	else 
	{
		for(i=0;i<dim;i++) 
			MPI_Recv(m[i],n,MPI_INT,0,1,MPI_COMM_WORLD,&status);
	}
	rap=n/numtasks;

	MPI_Barrier(MPI_COMM_WORLD);
	time1 = MPI_Wtime();
	
	//Distributed Floyd
	for(k=0;k<n;k++)
	{
		root=k/rap;
		if(root>numtasks-1)
			root=numtasks-1;
		if(root==rank)
		{
			MPI_Bcast(m[k-root*rap],n,MPI_INT,root,MPI_COMM_WORLD);
			memmove(line,m[k-root*rap],n*sizeof(int));
		}
		else
			MPI_Bcast(line,n,MPI_INT,root,MPI_COMM_WORLD);
		
		for(i=0;i<dim;i++)
			for(j=0;j<n;j++)
				if(m[i][k]+line[j]<m[i][j])
					m[i][j]=m[i][k]+line[j];
		MPI_Barrier(MPI_COMM_WORLD);
	}
	MPI_Barrier(MPI_COMM_WORLD);
	time2=MPI_Wtime();
	if(rank==0)
		printf("Time elapsed is %lf\n",time2-time1);
	
	//Matrix assembly
	if(rank!=0)
		for(i=0;i<dim;i++)
			MPI_Send(m[i],n,MPI_INT,0,1,MPI_COMM_WORLD);
	else
	{
		if(numtasks>1)
		{
			next=dim;
			for(i=1;i<numtasks-1;i++)
			{
				for(j=0;j<dim;j++)
					MPI_Recv(m[next+j],n,MPI_INT,i,1,MPI_COMM_WORLD,&status);
				next+=dim;
			}
			for(i=0;i<strip;i++)
				MPI_Recv(m[next+i],n,MPI_INT,numtasks-1,1,MPI_COMM_WORLD,&status);
		}
	}
	
	if(rank==0)
	{
		FILE *f=fopen("royfloyd2.out","w");
		for(i=0;i<n;i++)
		{
			for(j=0;j<n-1;j++)
			{
				if(m[i][j]==lim)
					m[i][j]=0;
				fprintf(f,"%i ",m[i][j]);
			}
			if(m[i][n-1]==lim)
				m[i][n-1]=0;
			fprintf(f,"%i\n",m[i][n-1]);
		}
		fclose(f);
		for(i=0;i<n;i++)
			free(m[i]);
	}
	else
		for(i=0;i<dim;i++)
			free(m[i]);
	free(m);
	free(line);
	MPI_Finalize();	
	return 0;
}