// Folyd.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <memory.h>
#include <time.h>
void Floyd(int *inputrect,int n,int *&outputrect);
int main(int argc, char* argv[])
{
	
	FILE *fp=fopen("E:\\data\\pmed40.dimacs","r");
	char c;
	int	nodenum;
	int pathnum;
	int average;
	fscanf(fp,"%c",&c);
	fscanf(fp,"%d",&nodenum);
	fscanf(fp,"%d",&pathnum);
	fscanf(fp,"%d\n",&average);
	int *test=new int[nodenum*nodenum];
	memset(test,-1,sizeof(int)*nodenum*nodenum);
	for(int i=0;i<pathnum;i++)
	{
		int node1,node2,power;
		fscanf(fp,"%c",&c);
		fscanf(fp,"%d",&node1);
		fscanf(fp,"%d",&node2);
		fscanf(fp,"%d\n",&power);
		test[node1*nodenum+node2]=power;
	}
	fclose(fp);
	int *output;
	long t,t1;
	time(&t);
	Floyd(test,nodenum,output);
	printf("%ld",time(&t1)-t);
	fp=fopen("E:\\data\\resultrect.dat","w");
	fwrite(output,sizeof(int),nodenum*nodenum,fp);
	fclose(fp);
	
	
	/*
	int test[9]={
						0,2,2,
						1,0,-1,
						4,-1,0
						};*/
	/*
	int test[9]={	 0,3,4,
					 2,0,-1,
					 4,-1,0
					};
		int *output;
		Floyd(test,3,output);
		printf("Hello World!\n");*/

	
	return 0;
}
void Floyd(int *inputrect,int n,int *&outputrect)
{
	outputrect=new int[n*n];
	memcpy(outputrect,inputrect,sizeof(int)*n*n);
	for(int k=0;k<n;k++)
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
				int m1=outputrect[k*n+j];
				int m2=outputrect[i*n+k];
				if(m1<0||m2<0)
					continue;
				int b=outputrect[i*n+j];
				int a=m1+m2;
				if(a<b||b<0) outputrect[i*n+j]=a;
			
		}
	}
}