// Dijkstra's Algorithm in C using a table with the best S vertex for
// every T vertex.
// See CSE 2320 Notes 14

#include <stdio.h>
#include <stdlib.h>
// For getrusage()
#include <sys/time.h>
#include <sys/resource.h>

// Basic Definitions

#define oo (1000000000)

// Declarations

int numVertices,numEdges;
struct edge {
  int tail,head,weight;
  int next;  // subscript of next edge with same tail 
};
typedef struct edge edgeType;
edgeType *edgeTab;
int *firstEdge;  // Table indicating first edge for a tail

float CPUtime()
{
struct rusage rusage;

getrusage(RUSAGE_SELF,&rusage);
return rusage.ru_utime.tv_sec+rusage.ru_utime.tv_usec/1000000.0
       + rusage.ru_stime.tv_sec+rusage.ru_stime.tv_usec/1000000.0;
}

void read_input_file()
{
// Reads a file with a weighted, directed graph and
// stores as unordered adjacency lists.
int tail,head,weight,i,j,workingEdges;

// read number of nodes and edges
scanf("%d %d",&numVertices,&numEdges);

firstEdge=(int*) malloc(numVertices*sizeof(int));
edgeTab=(edgeType*) malloc(numEdges*sizeof(edgeType));
if (!firstEdge || !edgeTab)
{
  printf("edgeTab malloc failed %d\n",__LINE__);
  exit(0);
}

// Initially, all adjacency lists are empty
for (i=0;i<numVertices;i++)
  firstEdge[i]=(-1);

// read edges, each with a weight
workingEdges=0;
for (i=0; i<numEdges; i++)
{
  scanf("%d %d %d",&tail,&head,&weight);
  // Test for illegal edge.
  if (tail<0 || tail>numVertices-1 || head<0
  || head>numVertices-1 || weight<=0)
  {
    printf("Invalid input %d %d %d at %d\n",tail,head,weight,__LINE__);
    exit(0);
  }
  // Save input edge and insert in adjacency list
  edgeTab[workingEdges].tail=tail;
  edgeTab[workingEdges].head=head;
  edgeTab[workingEdges].weight=weight;
  edgeTab[workingEdges].next=firstEdge[tail];
  firstEdge[tail]=workingEdges;
  workingEdges++;
}
}

void dijkstra()
{
typedef enum {s,t} stType;

int i,j,SPedgeCount=0,smallestDist,smallestVertexNumber;
stType *flag;
int *Tdist,*bestSneighbor,*dist;

flag=(stType*) malloc(numVertices*sizeof(stType));
Tdist=(int*) malloc(numVertices*sizeof(int));
bestSneighbor=(int*) malloc(numVertices*sizeof(int));

if (!flag || !Tdist || !bestSneighbor)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
// Vertex 0 starts in S.  Other vertices start in T.
flag[0]=s;
for (i=1;i<numVertices;i++)
  flag[i]=t;

// Initialize T-table with edges from vertex 0.
for (i=0;i<numVertices;i++)
  Tdist[i]=oo;
for (i=firstEdge[0];
     i!=(-1);
     i=edgeTab[i].next)
{
  Tdist[edgeTab[i].head]=edgeTab[i].weight;
  bestSneighbor[edgeTab[i].head]=0;
}

// Each iteration finds another SP tree edge
for (SPedgeCount=0;SPedgeCount<numVertices-1;SPedgeCount++)
{
  // Scan for minimum weight edge.
  smallestDist=oo;
  for (j=0;j<numVertices;j++)
    if (flag[j]==t && Tdist[j]<smallestDist)
    {
      smallestDist=Tdist[j];
      smallestVertexNumber=j;
    }
  if (smallestDist==oo) // no edges remain that bridge S & T
    break;

  printf("Include edge from %d to %d to give distance %d\n",
    bestSneighbor[smallestVertexNumber],smallestVertexNumber,
    smallestDist);
  flag[smallestVertexNumber]=s;

  // Scan adjacency list looking for improvements
  for (j=firstEdge[smallestVertexNumber];
       j!=(-1);
       j=edgeTab[j].next)
    if (flag[edgeTab[j].head]==t
    && Tdist[smallestVertexNumber]+edgeTab[j].weight<Tdist[edgeTab[j].head])
    {
      Tdist[edgeTab[j].head]=Tdist[smallestVertexNumber]+edgeTab[j].weight;
      bestSneighbor[edgeTab[j].head]=smallestVertexNumber;
    }
}
if (SPedgeCount<numVertices-1)
  for (i=1;i<numVertices;i++)
    if (flag[i]==t)
      printf("Vertex %d is not reachable from vertex 0\n",i);
free(flag);
free(Tdist);
free(bestSneighbor);
}

int main()
{
int i,j;
float startCPU,stopCPU;

read_input_file();
startCPU=CPUtime();
dijkstra();
stopCPU=CPUtime();
printf("Table-based Dijkstra's time %f\n",stopCPU-startCPU);
free(edgeTab);
free(firstEdge);
}