//Author Antonio-Gabriel Sturzu

#include<stdio.h>
#include<mpi.h>
#include<string.h>
#include<stdlib.h>
#define inf 50000001

int main(int argc,char *argv[])
{
	int rc,numtasks,rank,**m,n,*line,dim,next=0,strip,*d,minl,ming,iminl,iming,prod;
	int i,j,temp;
	char *viz;
	double time1,time2;
	FILE *f;
	MPI_Status status;

	//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)
	{	
		f=fopen("dijkstra.in","r");
		fscanf(f,"%i",&n);
	}
	//Broadcast n's value to all processes
	MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);
	dim=n/numtasks;
	strip=dim;
	if(rank==numtasks-1 && n%numtasks!=0)
		dim=n-dim*(numtasks-1);
	
	//Partition the data

	m=(int **) calloc(n*dim,sizeof(int *));
	for(i=0;i<n;i++)
			m[i]=(int *) calloc(dim,sizeof(int));
	if(rank==0)
	{
		line=(int *) calloc(n,sizeof(int));
		for(i=0;i<n;i++)
		{
			next=dim;
			for(j=0;j<n;j++)
				fscanf(f,"%i",line+j);
			memmove(m[i],line,dim*sizeof(int));
			for(j=1;j<numtasks-1;j++)
			{
				MPI_Send(&line[next],dim,MPI_INT,j,1,MPI_COMM_WORLD);
				next+=dim;
			}
			if(numtasks>1)
				MPI_Send(&line[next],n-next,MPI_INT,numtasks-1,1,MPI_COMM_WORLD);
		}
	}		
	else
		for(i=0;i<n;i++)
			MPI_Recv(m[i],dim,MPI_INT,0,1,MPI_COMM_WORLD,&status);

	d=(int *) calloc(dim,sizeof(int));
	viz=(char *) calloc(dim,sizeof(char));

	MPI_Barrier(MPI_COMM_WORLD);
	time1 = MPI_Wtime();

	//Initialize local distance vectors

	if(rank!=0)
	{
		for(i=0;i<dim;i++)
			d[i]=inf;
	}
	else
	{
		for(i=1;i<dim;i++)
			d[i]=inf;
		d[0]=0;
	}
	MPI_Barrier(MPI_COMM_WORLD);

	//Distributed Dijkstra's algorithm
	for(;;)
	{
		minl=inf;
		for(i=0;i<dim;i++)
			if(viz[i]==0 && d[i]<minl)
			{
				minl=d[i];
				iminl=i;
			}
		//Determine the global minimum distance from a node to the source
		MPI_Allreduce(&minl,&ming,1,MPI_INT,MPI_MIN,MPI_COMM_WORLD);
		if(ming==inf)
			break;
	
		if(minl==ming)
		{
			if(rank!=numtasks-1)
				temp=iminl+rank*dim;
			else
				temp=iminl+rank*strip;
			MPI_Allreduce(&temp,&iming,1,MPI_INT,MPI_MIN,MPI_COMM_WORLD);
		}
		else
			MPI_Allreduce(&n,&iming,1,MPI_INT,MPI_MIN,MPI_COMM_WORLD);
	
		//If the node with the minimum distance is owned by this process
		//mark it as visited
		
		if(rank!=numtasks-1)
		{
			if(iming>=rank*dim && iming<(rank+1)*dim)
				viz[iming-rank*dim]=1;
		}
		else
		{
			if(iming>=rank*strip && iming<n)
				viz[iming-rank*strip]=1;
		}
		for(i=0;i<dim;i++)
		{
			if(m[iming][i]+ming<d[i] && m[iming][i]!=-1)
				d[i]=m[iming][i]+ming;
		}
		MPI_Barrier(MPI_COMM_WORLD);
	}
	MPI_Barrier(MPI_COMM_WORLD);
	time2 = MPI_Wtime();
	if(rank==0)
		printf("Au trecut %f secunde\n",time2-time1);

	if(rank==0)
		printf("The minimum distances are :\n");
	MPI_Barrier(MPI_COMM_WORLD);
	if(rank!=numtasks-1)
		prod=rank*dim;
	else
		prod=rank*strip;

	for(i=0;i<dim;i++)
	{
		if(d[i]==inf)
			d[i]=0;
		printf("%i %i\n",i+prod+1,d[i]);
	}
	for(i=0;i<n;i++)
		free(m[i]);
	free(m);
	free(d);
	free(viz);
	if(rank==0)
		free(line);
	MPI_Finalize();	
	return 0;
}