#include<stdio.h>
#include<mpi.h>
#include<time.h>

int main(){
	int path[6][6] = { {0,2,5,9999,9999,9999},
					   {9999,0,7,1,9999,8},
					   {9999,9999,0,4,9999,9999},
					   {9999,9999,9999,0,3,9999},
					   {9999,9999,2,9999,0,3},
					   {9999,5,9999,2,4,0}	};
	double start,end;
	start = clock();
	MPI_Init(NULL,NULL);
	int size;
	int rank;
	MPI_Comm_rank(MPI_COMM_WORLD,&rank);
	MPI_Comm_size(MPI_COMM_WORLD,&size);
	for(int k=0;k<6;k++){
		if(rank!=0){
			MPI_Recv(path,36,MPI_INT,rank-1,0,MPI_COMM_WORLD,MPI_STATUS_IGNORE);
		}
		for(int i=0;i<6;i++){
			for(int j=0;j<6;j++){
				int temPath = path[i][k] + path[k][j];
				path[i][j] = (path[i][j]<temPath) ? path[i][j] : temPath;
			}
		}
		MPI_Send(path,36,MPI_INT,(rank+1)%size,0,MPI_COMM_WORLD);
		if(rank==0){
			MPI_Recv(path,36,MPI_INT,size-1,0,MPI_COMM_WORLD,MPI_STATUS_IGNORE);
		}
	}
	if(rank==0){
		end = clock();
		for(int i=0;i<6;i++){
			for(int j=0;j<6;j++){
				printf("%6d\n",path[i][j]);
			}
			printf("%.61f ms",((double) (end-start)/CLOCKS_PER_SEC));
		}
		MPI_Finalize();
	}
	return 0;
}