#include <omp.h>
#include <stdio.h>
#include <sys/time.h>

#define INFINITE 998
#define CHUNKSIZE 1 /*defines the chunk size as 1 contiguous iteration*/

int MAX;

int allselected(int *selected)
{
    int i;
    for(i=0;i<MAX;i++)
        if(selected[i]==0)
            return 0;
    return 1;
}
void shortpath(int cost[][1000],int *preced,int *distance)
{
    int selected[1000]={0};
    int current=0,i,k,dc,smalldist,newdist;
    for(i=0;i<MAX;i++)
       distance[i]=INFINITE;
    selected[current]=1;
    distance[0]=0;
    current=0;
    #pragma omp parallel private(k,smalldist,newdist,current)
    {
        while(!allselected(selected))
        {
                smalldist=INFINITE;
                dc=distance[current];
                #pragma omp parallel for schedule(dynamic, CHUNKSIZE)
                for(i=0;i<MAX;i++)
                {
                        if(selected[i]==0)
                        {
                                newdist=dc+cost[current][i];
                                if(newdist<distance[i])
                                {
                                        //#pragma omp critical
                                        {
                                                distance[i]=newdist;
                                        }
                                        preced[i]=current;
                                }
                                if(distance[i]<smalldist)
                                {
                                        //#pragma omp critical
                                        {
                                                smalldist=distance[i];
                                        }
				k=i;
                                }
                        }
                }
                current=k;
                //#pragma omp critical
                {
                        selected[current]=1;
                }
        }
    }
}

int main()
{
            int th_id, nthreads;
        struct timeval time1;
        struct timeval time2;
	int cost[1000][1000];

        FILE * pFile;
        int n,k,i,j;

  i=0;j=0;
  pFile = fopen ("Di1000.txt","r");
  if(pFile != NULL)
        fscanf (pFile, "%d", &n);
  MAX = n;
  for(i=0;i<MAX;i++)
        for(j=0;j<MAX;j++)
                cost[i][j]=INFINITE;
  while(fscanf(pFile,"%d",&i)!=EOF)
  {
	fscanf (pFile, "%d", &j);
	fscanf (pFile, "%d", &cost[i][j]);
   }
  fclose (pFile);

int preced[1000]={0},distance[1000];
        gettimeofday(&time1,NULL);
    shortpath(cost,preced,distance);
        gettimeofday(&time2,NULL);

        printf("time: %ld\n",time2.tv_usec-time1.tv_usec);

    return 0;
}