/* Problem 8--DOT
   This is a straightforward application of Dijkstra's algorithm.  There
   was a certain amount of tediousness, however, in reading the input
   in the proper format. */

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

typedef char CT[18];

typedef struct ELT { /* How far apart a given city is from another */
 int node, len;
 struct ELT *next;
} ELT;

typedef struct ELN { /* Each city has an adjacency list */
 int back, plen, inf, coll;
 /* Each node contains a back pointer to the previous node in the path,
    a path length from the starting node, flags indicating whether the
    path length is infinite and whether it has already been added to the
    collection. */
 ELT *head; /* The head of the linked list of adjacent nodes. */
} ELN;

FILE *in, *out;
ELN *AdjList;
int size;

int main (int argc, char **argv);
int CTcmp (const void *a, const void *b);
int ReadCity (CT City);
void FreeELT (ELT *p);
void FreeList (void);
void Dijkstra (int p1, int p2);

int main (int argc, char **argv) {

  CT *Cities, City1, City2, temp;
  void *pos1, *pos2;
  int i, dist, p1, p2;
  ELT *entry;

 in = fopen ("prob8.in","r");
 out = fopen ("prob8.out","w");
 fscanf (in,"%d",&size); /* Get number of cities. */
 Cities = malloc (size*sizeof(CT));
 AdjList = calloc (size,sizeof(ELN));
 fgets(temp,18,in); /* Skip EOLN. */
 for (i=0;i<size;i++) { /* Read in cities. */
  fgets(Cities[i],18,in);
  Cities[i][strlen(Cities[i])-1] = 0; /* Kill EOLN */
 }
 qsort (Cities,size,sizeof (CT),CTcmp); /* Sort cities */
 while (1) {
  ReadCity(City1);  /* Read in Cities until the EOD is reached */
  ReadCity(City2);
  fscanf (in,"%d",&dist);
  if (strcmp (City1,"EOD")==0 && strcmp (City2,"EOD")==0) break;
  pos1 = bsearch (City1,Cities,size,sizeof(CT),CTcmp);
  p1 = (CT*)pos1-Cities; /* Get City Number */
  pos2 = bsearch (City2,Cities,size,sizeof(CT),CTcmp);
  p2 = (CT*)pos2-Cities;
  entry = malloc (sizeof (ELT)); /* Add information to adjacency lists*/
  entry->node = p2;              /* for both cities. */
  entry->len = dist;
  entry->next = AdjList[p1].head;
  AdjList[p1].head = entry;
  entry = malloc (sizeof (ELT));
  entry->node = p1;
  entry->len = dist;
  entry->next = AdjList[p2].head;
  AdjList[p2].head = entry;
 }
 while (!ReadCity (City1)) { /* Read in cities to find detour */
  ReadCity (City2);
  pos1 = bsearch (City1,Cities,size,sizeof(CT),CTcmp);
  p1 = (CT*)pos1-Cities;
  pos2 = bsearch (City2,Cities,size,sizeof(CT),CTcmp);
  p2 = (CT*)pos2-Cities;
  Dijkstra (p1,p2); /* Run Dijkstra's algorithm on these cities */
  fprintf (out,"Detour from %s to %s\n",Cities[p2],Cities[p1]);
  for (i=p2;i != -1; i = AdjList[i].back)
   fprintf (out,"%s\n",Cities[i]);
  fprintf (out,"Total distance: %d miles\n\n",AdjList[p2].plen);
 }
 free (Cities);
 FreeList ();
 return EXIT_SUCCESS;
}

/* CTcmp is a standard string comparison function for sorting. */
int CTcmp (const void *a, const void *b) {
 return strcmp ((char *)a,(char *)b);
}

/* ReadCity reads in a city name from the keyboard.  It returns 1 if EOF
   is reached, 0 otherwise. */
int ReadCity (CT City) {

  CT temp;
  int l,c;

 if (EOF==fscanf (in,"%s",temp)) return 1;
 if (temp[0]!='\"') { /* if it didn't begin with " */
  strcpy (City,temp);
  return 0;
 }
 strcpy (City,&temp[1]); /* otherwise, keep reading until " is found. */
 l = strlen (City);
 while ((c=fgetc(in)) != '\"') City[l++]=c;
 City[l]=0;
 return 0;
}

/* FreeELT frees up the memory stored by the adjacency list. */
void FreeELT (ELT *p) {

 if (p==NULL) return;
 FreeELT (p->next);
 free (p);
}

/* FreeList frees up the adjacency list data structure. */
void FreeList (void) {

  int i;

 for (i=0;i<size;i++) FreeELT (AdjList[i].head);
 free (AdjList);
}

/* Dijkstra runs Dijkstra's algorithm on the adjacency list looking for
   a path between p1 and p2 */
void Dijkstra (int p1, int p2) {

  int i, minlen=0, minnode=0, found, n;
  ELT *P;

 for (i=0;i<size;i++) { /* Assume all nodes are an infinite distance*/
  AdjList[i].inf = 1;   /* away and none have been added to our */
  AdjList[i].coll = 0;  /* collection yet. */
 }
 AdjList[p1].inf = AdjList[p1].plen = 0; /* p1 is adjacent to itself. */
 AdjList[p1].back = -1; /* The back pointer for p1 points nowhere. */
 while (1) {
  found = 0; /* look for the nearest node to add to the collection */
  for (i=0;i<size;i++) {/*Skip if its infinitely away or already there*/
   if (AdjList[i].inf || AdjList[i].coll) continue;
   if (found && AdjList[i].plen >= minlen) continue;
   minlen = AdjList[i].plen;
   minnode = i;
   found = 1;
  }
  if (minnode==p2) break; /* If this nearest node is p2, we're done. */
  AdjList[minnode].coll = 1; /* Otherwise, add it to the collection. */
  for (P=AdjList[minnode].head;P!=NULL;P=P->next) {
   n = P->node; /* go through everything connecting to the minnode */
   if (AdjList[n].coll) continue; /* Skip if already found */
   if (minnode==p1 && n==p2) continue; /* Ignore the p1->p2 connection*/
   if (AdjList[n].inf||AdjList[n].plen>AdjList[minnode].plen + P->len) {
    AdjList[n].inf = 0;/* If we found a shorter path, adjust the path*/
    AdjList[n].plen = AdjList[minnode].plen + P->len;
    AdjList[n].back = minnode; /* length and set the back pointer */
   }
  }
 }
}