#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>

/* Code to generate the essential subgraph H of a random uniform graph G */
/* By C. McGeoch, modified 5/10 for AlgLab                               */
/*  The initial version 1: memoization with a distance matrix  */  

/* Inputs (one per line): */
/*   nodes n              */
/*   trials t             */
/*   seed s     (optional)*/

/* Output: (all on one line)       */
/* Trial number, G.nodes, G.edges, */
/* Edges in H                      */
/* Cost of last edge in H          */
/* Rank (in G) of last edge in H   */
/* Rank (in G) of largest MST edge */
/* MST Diameter                    */ 

#define Assert( cond , msg ) if ( ! (cond) ) {printf("msg \n"); exit(1);} ; 

#define MAXNODES 1601
#define MAXEDGES 1279201 
#define TRUE 1
#define FALSE 0 
#define INFINITY -9999999.0

typedef char string[50]; 

double dmatrix[MAXNODES][MAXNODES]; 

/*-------------------------------------------------------------------------*/
/* Definitions for G and E graphs                                          */
/*-------------------------------------------------------------------------*/
typedef struct edgestr {       /*  Edges of essential subgraph (adj list) */
  int dest;
  double cst; 
  struct edgestr *next; 
} edgetype ; 


typedef struct nodestr {        /* Nodes of essential subgraph */
  edgetype *first;
  edgetype *last; 
} nodetype;


typedef struct {       /* Edges in random generated graph  */ 
   int vv;
   int ww;
   double cost; 
 } gedgetype; 

int edgecount;                    /* Number edges generated */ 
int edgeindex;                    /* index in edge array of G*/ 
double curmax;
double mydrand(); 
double drand48(); 

gedgetype edgeset[MAXEDGES];      /*  Edges of G */ 
nodetype nodelist[MAXNODES];      /*  Nodes of E*/ 

/*-----------------------------------------------------*/
/* Global parameters and param table                   */
/*-----------------------------------------------------*/
int nodes, trials, seed;  

int totedges; 
int rand_seed;       /*boolean for random or supplied seed*/ 
string cmdtable[10]; 
int cmdtable_size; 


/*-------------------------------------------------------*/ 
/*  Input Handlers and Misc.                             */ 
/*-------------------------------------------------------*/
/*--------------tabinit-------------------------*/
void tabinit()
{
  cmdtable_size = 3; 

  strcpy(cmdtable[0], "sentinel.spot"); 
  strcpy(cmdtable[1], "nodes");
  strcpy(cmdtable[2], "trials");
  strcpy(cmdtable[3], "seed"); 
  nodes=MAXNODES;
  trials=1;
  rand_seed = TRUE;  
}
/*------------lookup command in table------------ */ 
int lookup (cmd) 
string cmd;  
{
  /* lookup commands in command table */ 
  int i; 
  int stop;  
  strcpy(cmdtable[0], cmd); 
  stop = 1; 
  for (i=cmdtable_size; stop != 0 ; i--) stop = strcmp(cmdtable[i], cmd); 
  return ( i+1 );
}/*lookup*/ 

/*------------translate input command---------------*/ 
void transinput() { 
  char cmd[50], buf[50];
  int index;  
  while (scanf("%s", cmd) != EOF ) { 
    fgets(buf, sizeof(buf), stdin);

    index = lookup (cmd);
    switch (index ) {
    case 0 : { printf("%s: Unknown command\n", cmd); 
	       break;
	     }
    case 1 : { sscanf( buf, "%d", &nodes);
	       Assert(1<=nodes && nodes<=MAXNODES , Nodes out of range. ); 
	       break;
	     }
    case 2: { sscanf( buf, "%d", &trials); 
	      break;
	    }
    case 3: { sscanf( buf, "%d", &seed); 
 	      rand_seed = FALSE; 
	      break; 
	    }
    }/*switch*/
  }/*while scanf */

  if (rand_seed == TRUE) srand48((int) time(0));
  else srand48(seed);

}/*transinput*/



/*--------------------------------------------------------------------------*/
/*  The Heap used for Dijkstra searches                                     */
/* -------------------------------------------------------------------------*/
typedef struct {    /* Heap elements */ 
  int hid;          /* node name  */ 
  double hval;      /* distance from src */ 
} heaptype;

int      heapsize;       /* heap is in locations 1..heapsize */ 
heaptype heap[MAXNODES];
int      hloc[MAXNODES]; /* location backpointers in heap   */ 


/* --heapinit -------initialize empty with one node,  dist = 0 */ 
void heapinit(int src) { 
  heap[1].hid = src;
  heap[1].hval = 0.0; 
  hloc[heap[1].hid] = 1; 
  heapsize = 1; 

} 
/*-------heapextract -----------------------------------------*/ 
heaptype heapextract() { 

  heaptype heaptop  = heap[1]; 

  heap[1] = heap[heapsize--]; 
  hloc[ heap[1].hid ]  = 1; 

  heaptype  tmp; 
  int hix = 1; 
  int lchild, rchild, which; 
  double min ; 


#ifdef HEAP 
  int i; 
  printf("removed %d %lf\n", heaptop.hid, heaptop.hval); 
  printf("heap before siftdown :\n");
  for (i = 1; i <= heapsize; i++) {
    printf("\t %d  %d  %d  %lf\n",i, hloc[heap[i].hid], heap[i].hid, heap[i].hval);
  }
#endif 

 /* siftdown */  
  while ( hix <  heapsize) {
    min = heap[hix].hval;
    which = hix; 

    lchild = hix*2; 
    if (lchild <= heapsize && heap[lchild].hval < min ) { 
      min = heap[lchild].hval;
      which = lchild; 
    }
    rchild = hix*2 + 1; 
    if (rchild <= heapsize && heap[rchild].hval < min) {
      min = heap[rchild].hval;
      which = rchild; 
    } 
    if (which == hix) break;
    else { /* swap */ 
      tmp = heap[hix];
      heap[hix] = heap[ which ]; 
      hloc[ heap[hix].hid] = hix; 

      heap[ which ] = tmp;
      hloc[ heap[which].hid ] = which;

      hix = which; 
    }
  }/* while */ 

#ifdef HEAP 
  printf("\n heap after siftdown (size %d) to  %d \n" , heapsize, hix); 
  for (i= 1; i <= heapsize; i++) 
    printf("%d  %d  %d  %lf \n", i , hloc[heap[i].hid], heap[i].hid,  heap[i].hval); 
  printf("*\n");
  fflush(stdout); 
#endif

  return heaptop;  }  /* extractmin */ 

/*---siftup from position hix ------------------------------------*/  
void siftup (int hix) { 

  heaptype tmp ; 

#ifdef HEAP
  int i; 
  printf("before siftup from location %d \n", hix);
  for (i = 1; i <= heapsize; i++) 
    printf("\t %d %d %d %lf \n",  i, hloc[heap[i].hid], heap[i].hid, heap[i].hval);
 
#endif 

  while (hix > 1) { 
    int parent = hix/2; 

    if ( heap[hix].hval  <  heap[ parent ].hval ) {
      tmp = heap[hix];
      heap[hix] = heap[parent];
      heap[parent] = tmp;

      hloc[ heap[hix].hid ] = hix;
      hloc[ heap[parent].hid] = parent;

      hix = parent;
    } else break;


  }/*while*/ 

#ifdef HEAP 
  printf("after siftup to location %d \n", hix);
  for (i = 1; i <= heapsize; i++) 
   printf("\t %d %d %d %lf \n",  i, hloc[heap[i].hid], heap[i].hid, heap[i].hval);
#endif 

}

/*---heapinsert------------------------------------------------*/ 
void heapinsert( int nodename, double dist ) {

  heapsize++;
  heap[heapsize].hid = nodename;
  heap[heapsize].hval = dist; 

  hloc[ nodename ] = heapsize;
  siftup( heapsize); 

#ifdef DEBUG_H
  printf("\n hinsert %d  %lf hsize %d \n", nodename, dist, heapsize); 
#endif

 }  /* insert new into heap */ 

/* -heapgetinx--------------------return index for query, update */ 
int heapgetinx (int node) { 
    return  hloc[node];  
} 

/*-heapgetdist----------------return distance for comparison    */ 
double heapgetdist( int inx) {
  return heap[ inx ].hval;
} 

/*heapdecreasekey-----------------------------------------------*/
void heapdecreasekey( int inx, double newval) { 
  heap[ inx ].hval = newval;
  siftup (inx);
} 

/*--------------------------------------------------------------------------*/
/*  Essential Subgraph distance calculation, insert, init                   */
/*--------------------------------------------------------------------------*/ 

typedef struct {            /* Maintain search status for nodes */ 
   int status;  
   double distance;     
 } searchtype; 
searchtype dnodes[MAXNODES];  /* For shortest-path search */ 

/*-----distance: search from s to d in E, return distance or infty          */ 
double distance(int s,int d, double ecost)  {

edgetype *nptr;
int ename;   
double edist; 
double curdist; 

 int  unseen = 0; 
 int  inheap = 1;
 int  seen = 2; 

#ifdef DEBUGSRC
 printf("start search unseen is %d \n", unseen); 
#endif 

 /*V1: use memoization*/ 
 if ((dmatrix[s][d] != INFINITY) && (dmatrix[s][d] < ecost)) 
     return dmatrix[s][d]; 

 int i ; 
 for ( i = 1; i <= nodes; i++) {
   dnodes[i].status =unseen;
   dnodes[i].distance = INFINITY;  /* from math.h */ 
 } 

 dnodes[s].status  = inheap; 
 dnodes[s].distance = 0.0; 

 /* initalize heap to source vertex */ 
 heapinit (s); 
 heaptype x;  
 
#ifdef DEBUGSRC
 printf("\t search from %d to %d ------\n", s, d); 
 fflush(stdout); 
#endif 

 while ( heapsize != 0 ) {
   x  = heapextract();

   /* V1: distance matrix */ 
   dmatrix[s][x.hid] = x.hval;
   dmatrix[x.hid][s] = x.hval; 

#ifdef DEBUGSRC
   printf("\t Extract %d  %lf \n", x.hid, x.hval);
   if (x.hid == d) printf("\t found it %d  %lf \n", x.hid, x.hval); 
   fflush(stdout); 
#endif 

   if (x.hid == d) return x.hval;  /* found it */  

   dnodes[x.hid].status = seen;
   curdist = x.hval; 

   /* for each neighbor e of x*/ 
   nptr = nodelist[x.hid].first;  

   while (nptr != NULL) {

     ename = nptr->dest;
     edist = curdist + nptr->cst;

#ifdef DEBUGSRC
     printf("\t %d has edge %d  %lf  status %d unseen %d \t", x.hid, ename, edist, dnodes[ename].status, unseen);
     fflush(stdout); 
#endif 

     if ( dnodes[ename].status == unseen) {

       heapinsert( ename, edist) ; 
       dnodes[ ename].status = inheap;
       
     }
     else if ( dnodes[ename].status == inheap ) {
       int heapx = heapgetinx(ename); 
       
       if (edist < heapgetdist( heapx) ) {
	 heapdecreasekey (heapx, edist) ; 
       }
     }/* else status = seen */ 
     nptr = nptr -> next;

   }/* fore each neaighbor */ 

 }/* while heapsize */ 

#ifdef DEBUGSRC
   printf("\t search is done \n");
   fflush(stdout); 
#endif 
   return INFINITY;  /* didn't find d reachible from s */  

}/*distance */ 

/*-------------insert---------------------------------------*/
void insert(int v, int w, double cost)  
{
  edgetype *newedge;
  edgetype *lptr; 

#ifdef DEBUGINS 
  printf("\t\t subgrinsert %d %d %lf\n", v, w, cost); 
     fflush(stdout); 
#endif 

  /* insert edge in v list */
   newedge = (edgetype *) malloc( sizeof(  edgetype  ) );
   newedge->dest = w; 
   newedge->cst = cost;
   newedge->next = NULL;
   if (nodelist[v].first == NULL) {
       nodelist[v].first = newedge;
     } else{
       lptr = nodelist[v].last;
       lptr->next = newedge;
     } 
    nodelist[v].last = newedge; 

   /* insert in w list */ 
   newedge = (edgetype *) malloc( sizeof( edgetype ) );
   newedge->dest = v; 
   newedge->cst = cost;
   newedge->next = NULL;
   if (nodelist[w].first == NULL) {
       nodelist[w].first = newedge;
     } else{
       lptr = nodelist[w].last;
       lptr->next = newedge;
     } 
   nodelist[w].last = newedge; 

}/*insert*/ 


/*-------------------------------------------------------------*/
/*       Generation of random edges and costs                  */ 
/*-------------------------------------------------------------*/

/*------------------mydrand-------------------------------------*/
double mydrand()
{
  return(drand48()); /* Reals on (0.0, 1.0]*/ 
} 
/*--------------- nextedge------------------------------------*/
/*  Return the next edge, v, w, cost                          */ 

void nextedge( int* v, int* w, double* cost)
{
  gedgetype  tmp = edgeset[edgeindex++];

  *v = tmp.vv;
  *w = tmp.ww;
  *cost = tmp.cost;
}

/*--dcompare-----------------------------------*/
/* for qsort                                   */ 
int dcompare( const void *a, const void *b) {
    
    gedgetype *aa = (gedgetype* ) a;
    gedgetype *bb = (gedgetype* ) b; 

    if ( aa->cost < bb->cost ) return -1;
    else if (aa-> cost > bb->cost ) return +1;
    else return 0;
} 

/*-----------------graphinit-------------------------------------------------------*/
/* S: initialize nodes (nodelist with edgeset empty                                */ 
/* S is an adjacency list, with edges doubled                                      */ 
/* G: is a list of random edges, in random vertex order                            */ 
/* The graph is undirected, nodes numbered 1..nodes, in array [1..nodes]           */
/*  There is one copy of each edge, oriented to indices (vv=lo, ww = hi)           */ 
/*  Sorted by edge cost                                                            */

void graphinit()
{
   int i, j, k;

   /* initialize node pointers for the subgraph E */ 
   totedges = nodes * (nodes-1) / 2; 
   for (i=1; i<= nodes; i++) {
	nodelist[i].first = NULL;
        nodelist[i].last = NULL;
      }
   
   /* initialize edges in the random input graph */ 
   k=0; 
   for (i=1; i<= nodes-1 ; i++) {
     for (j=i+1; j<= nodes; j++) {
         edgeset[k].vv= i; 
	 edgeset[k].ww = j;
         edgeset[k].cost = mydrand();  /* random uniform 0..1 */
         k++;
    }
   }
   /* sort the edges by cost */ 
   qsort (edgeset, totedges, sizeof(gedgetype), dcompare); 
   edgeindex = 0;     /* first edge returned*/ 

#ifdef DEBUGSRT
   for (i = 0; i < totedges; i++) 
     printf("%d \t %d \t %d \t %lf \n", i,edgeset[i].vv, edgeset[i].ww, edgeset[i].cost); 
     fflush(stdout); 
#endif 

}/*graphinit*/

/*---printsg for output  */ 
void printsg() {
  edgetype *nptr; 
  int ename; 
  double ecost; 
  int i; 
  int ctr; 
  
  /* The subgraph */ 
  for (i = 1; i <= nodes; i++) {
    printf("Node %d: \n ", i ); 
    ctr = 0; 
    nptr = nodelist[i].first; 
    while (nptr != NULL ) {
      ename = nptr->dest;
      ecost = nptr->cst; 
      printf("(%d  %lf) \t", ename, ecost); 
      nptr = nptr->next; 
      if (ctr % 10 == 0) printf("\n"); 
    }
    printf("\n");
  }
} 

/*---freesg for new trial  */ 
void freesg() {
  edgetype *nptr; 
  int i; 
  edgetype *nextedge;   

  /* The free subgraph */ 
  for (i = 1; i <= nodes; i++) {
    nptr = nodelist[i].first;
 
    while (nptr != NULL ) {
      nextedge = nptr->next; 
      free (nptr); 
      nptr = nextedge; 
    }

    nodelist[i].first = NULL;
    nodelist[i].last = NULL; 
  }
} 

/* V1: initialize the distance matrix */ 
void dminit() { 
  int i, j; 
  for (i = 1; i <= nodes; i++) 
    for (j= 1; j <= nodes; j++) dmatrix[i][j] = INFINITY; 
} 


/*----------------------------------------------*/ 
/*---------------------main---------------------*/ 
int main(int argc, char** argv)
{
  int DONE; 
  double ecost; 
  int v,w;
  int tr; 

  double  limit = 1.1;
  double lastcost = 1.1;
  int lastrank = totedges;
  int insertcount = 0;  
  double mindist; 

  tabinit();      
  transinput();   /* get input commands */ 

#ifdef DEBUG
  printf("input %d %d %d\n", nodes, trials, seed);
     fflush(stdout); 
#endif 
  
  for( tr= 0 ; tr< trials; tr++) {

    graphinit();     /* generate random graph, initialize subgraph */ 

    dminit(); /* V1: initialize the distance matrix*/ 

    limit =  1.1;   /* larger than any edge size */ 
    
    edgecount=0;           /* num generated: incremented in nextedge */ 
    insertcount = 0;       /* num in subgraph */
    lastcost = 0;          /* last edge in graph */
    lastrank = 0;          /* rank of last edge in graph */ 
  
    curmax = 1.0;          /* modified in nextcost */  

    DONE = FALSE;  
    while (!DONE) {        /* generate the subgraph */    

      nextedge(&v, &w, &ecost);    
      edgecount++; 
      mindist = distance(v,w, ecost);

#ifdef DEBUG
      printf("edge %d : (%d  %d %lf) dist %lf ", edgecount, v,w,ecost, mindist);
      if (mindist == INFINITY) printf("ins \n"); 
      else if (mindist > ecost) printf("ins \n");
      else printf("out \n"); 
     fflush(stdout); 
#endif 


     if ( (mindist == INFINITY)|| (mindist > ecost)) { 
            insert(v,w,ecost); 
            insertcount++; 
            lastcost = ecost;
	    lastrank = edgecount; 
     } 
   
     
     if (ecost > limit) DONE = TRUE;   
     if (edgecount >= totedges) DONE = TRUE; 

   }/*while still checking edges*/ 

#ifdef SEEOUTPUT 
    printsg();
    fflush(stdout); 
#endif 

  printf("%d %d %d   %d %lf %d  %lf\n", 
	 tr, nodes, totedges, insertcount, lastcost, lastrank,  limit);

  freesg(); 

  }/*for each trial */ 

  return 0; 
}/* main */