#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                               */
/*  Version 3: memoization with a distance matrix, plus filter  */  
/* Cleaned up version2, but no time changes. */ 
/*  Version 3 also includes BFS with loop abort and filter */ 

/* 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 2001
#define MAXEDGES 2001000

#define TRUE 1
#define FALSE 0 
#define INFTY 999999999.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);
} 


int    queue[MAXNODES]; // bfs queue
double qdist[MAXNODES];  //bfs queue 
int    qstat[MAXNODES]; // status in queue or not 
double ubdiam; 
/*-----bfs-------------------------------------------------------*/
/*---------------------------------------------------------------*/ 

double bfs (int s, int d, double ecost, int rule) { 
  // search from s to d in the graph, using BFS. 
  // 1. up to limit ecost, or INFTY, filling in dmatrix for s. 
  // 2. up to finding d, filling in dmatrix for s. 
  // 3. up to component size, filling in dmatrix for row s.  Return distance to d if found.  if < nodes, diam ub is infty; or ub is twice max distance. 

  int inqueue = 1; 
  int outqueue = 0 ; 
  int i; 
  for (i = 1; i <= nodes; i++) qstat[i] = outqueue; 

  queue[0] = s;  
  qdist[0] = 0.0; 
  qstat[s] = inqueue; 
  int qfront = 0;  // inv: location of first item in q 
  int qback =  1;  // inv: next item goes here 

  int curnode;  
  double curdist; 
  double maxdist = 0.0; 

  double sddist = INFTY;  // default incase not found 
  //  ubdiam = INFTY;         // default incase not connected 
  int nodecount = 0; 

#ifdef DEBUGBFS
  printf("bfs %d %d %lf %lf \n" , s, d, ecost, ubdiam); 
#endif 

  while ( qfront < qback ) {   /* while not empty */ 
    // inv: heap is in q[qfront .. qback-1] 

    curnode = queue[qfront];    // dequeue 
    curdist = qdist[qfront]; 
    qfront++; 
    nodecount++; 

#ifdef DEBUGBFS
      printf("\t dm %d %d %lf   %lf \n", s, curnode, dmatrix[s][curnode], curdist); 
#endif 

    // update dmatrix 
    if ((dmatrix[s][curnode] == INFTY) ||  (dmatrix[s][curnode] > curdist)) { //every distance found is an ub on true distance-- make it better
      dmatrix[s][curnode] = curdist;
      dmatrix[curnode][s] = curdist;
    }

    if (curnode == d) {     // found it
      sddist = curdist; 
      if (rule == 2) return sddist;      
    }
    if (curdist > ecost) { 
      if (rule == 1) return curdist;    // dist will be bigger than ecost (non-essential).  Return curdist.  
    }
    edgetype *nptr; 
    int ename; 
    double edist; 

   /* for each neighbor e of curnode: add distance and put in queue*/ 

   nptr = nodelist[curnode].first;  
   while (nptr != NULL) {
     ename = nptr->dest;
     edist = curdist + nptr->cst;

     if (edist > maxdist) maxdist = edist;  // longest distance s to any x. 
     if ( qstat[ename] == outqueue ) {  // ename not in queu already 
       
       queue[qback] = ename; 
       qdist[qback]=edist;      
       qback++; 
       qstat[ename] = inqueue; 
     }
     nptr = nptr -> next;
     
   }/* for each neighbor */ 
  }// while qnot eempty 

  // queue is empty, and we haven't returned yet. Either not connected to d, or rule 3 applies. 
  // either way sdist is correct finite (if found) or infinite if not found

  if (nodecount >=  nodes-1) {
    if (2*maxdist < ubdiam) ubdiam = 2*maxdist; 
  } 
#ifdef DEBUGBFS
  printf("\t diam %lf \n", ubdiam); 
#endif 

  return sddist; 
}// bfs

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

int diamcheck[MAXNODES]; 
int bfsworks = 0; 
/*-----distance: search from s to d in E, return distance or infty      */ 
/*                                                                      */ 
double distance(int s,int d, double ecost,  int ssize )  {

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

  int  unseen = 0; 
  int  inheap = 1;
  int  seen = 2; 
  int status[MAXNODES];  /* For shortest-path search */ 

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

  double sddist = INFTY; 

  if (ssize >= nodes-1) { // if connected, bfs to find a ub on diameter, and a guess for sdist 
    if (diamcheck[s] == 0)  { // havent yet checked diameter for s 
      diamcheck[s] = 1; 
      sddist = bfs ( s, d, ecost, 3);  // return ub on d, also go to component and figure out ubdist 
      if ((sddist == INFTY) || (sddist <= ecost)) bfsworks ++; 
      if (sddist == INFTY ) return INFTY; // its essential 
      if (sddist <= ecost) return sddist; // its non-essential

    }//
  } // if 

  // if the sddist is INFINTY the edge is essential.  No Dijkstra search. 
  // else ssdist is finite. 
  // if the ub sddist is less than or equal to ecost, the edge is non-essential.  
  //           No dijkstra search.  
  //           (rule 3) continue on to check the diameter.  
  //           all distances found are ubs on final distance s to d:
  //           all distances found x via s to y are ubs on final distance: 
  //           If diameter ub is non-infinity, and less than ecost, the program is done. 
  // 
  // Dijkstra search, using ecost to filter. 

  /* begin dijkstra search */ 
  int i; 
  for (i = 1; i <= nodes; i++) {
    status[i] = unseen; 

  } 
  status[s] = inheap;

  /* initalize heap to source vertex */ 
  heapinit (s); 
  heaptype x;  
 
  while ( heapsize != 0 ) {
    x  = heapextract();

   /* V1: distance matrix */ 
   dmatrix[s][x.hid] = x.hval;
   dmatrix[x.hid][s] = x.hval; 
 
   if (x.hid == d) return x.hval;  /* found it */  

   /* V2: abort the loop if this lb on distance to w is too big */ 
   /* V2 is faster if this tuneup is not used */  
   // if (x.hval > ecost) return x.hval; 
   status[x.hid] = 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;

     /* V2: filter the data structure */ 
     if ( edist > ecost );      /* skip it */
     else
       if (status[ename] == unseen) { 
	 heapinsert( ename, edist) ; 
	 status[ename] = inheap; 
     }
     else if (status[ename]==inheap) {
       int heapx = heapgetinx(ename); 
       if (edist < heapgetdist( heapx ) ) {
	 heapdecreasekey (heapx, edist) ; 
       }
     }/* else status = seen */ 
     nptr = nptr -> next;
     
   }/* for each neaighbor */ 
  }/* while heapsize */ 

  return INFTY;  /* 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++) diamcheck[i] = 0; 
  for (i = 1; i <= nodes; i++) 
    for (j= 1; j <= nodes; j++) dmatrix[i][j] = INFTY; 
} 


/*----------------------------------------------*/ 
/*---------------------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 */ 

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

    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, insertcount);

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


     if ( (mindist == INFTY)|| (mindist > ecost)) { 
            insert(v,w,ecost); 
            insertcount++; 
            lastcost = ecost;
	    lastrank = edgecount; 
     } 

     if (ubdiam != INFTY) limit = ubdiam; 

     if (ecost > limit) DONE = TRUE;   
     if (edgecount >= totedges) DONE = TRUE; 

   }/*while still checking edges*/ 

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

    //    printf("bfs works %d   ubdiam %lf\n", bfsworks, ubdiam); 
    bfsworks =0; 
    ubdiam= INFTY; 

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

  freesg(); 

  }/*for each trial */ 

  return 0; 
}/* main */