void dij( int rootref, string endCity, string endSt, graf& g)
{
    intersections * root = g.interArr[rootref];         // interArr is an array of intersection nodes
    Q * kyu = new Q(20000);                             // create priority queue (min heap)
    double totalDist = 0;                               // initialize total distance to zero
    kyu->insert(root);                                  // insert root into priority queue

    while(!kyu->isEmpty())                              // while queue is not empty
    {
       intersections * popped = kyu -> extractMin();    // extract top of queue
       popped->visited = 1;                             // mark as visited
       if(popped->nearestCity == endCity && popped->state==endSt)
           break;
       int connSize = popped->c;                        // get size of array containing refference

       for(int i = 0; i<connSize;i++)                   //    points to connecting intersections
       {
           int reff = popped->adjacents[i]->B;          // get refference for adjacent vertex
           double d = popped->adjacents[i]->distance;   // get distance from popped node to adjacent vertex
           if(g.interArr[reff]->visited==0)             // if adjacent vertex has not been visited
           {
              double alt = d + totalDist;               // measure distance from root to this vertex
              if(alt<g.interArr[reff]->dijDist)         // if this distance is less than dijDist (initialized very high)
              {
                  g.interArr[reff]->dijDist = alt;      // update dijDist distance
                  totalDist = alt;                      // update total distance
                  kyu->insert(g.interArr[reff]);        // insert into priority queue
              }

           }
       }
    }
}

struct graf{
      intersections ** interArr;
      graf(){}
      void make()
      {
           interArr = new intersections*[29146];
      }

      void insert(double la, double lo, double dist, string na,string st, int entry)
      {
          interArr[entry] = new intersections(la,lo,dist,na,st);
          interArr[entry]->visited = 0; interArr[entry]->dijDist = 10000000;
      }
}

struct intersections{
     double lat, lon, distanceToNearestPlace;
     string nearestCity, state;
     connections ** adjacents;
     double c, dijDist, visited;
     intersections * next, *prev;

     intersections(){
         c = 0;
         next = NULL; dijDist = 10000000; visited = 0; prev =NULL;
         adjacents = new connections*[24];
         for(int i = 0; i<24; i++)
             adjacents[i] = new connections;
     }
      intersections(double la, double lo, double dist, string nc, string st)
     {   lat = la; lon = lo; distanceToNearestPlace = dist; nearestCity = nc; state = st;
         c = 0; dijDist = 10000000; visited = 0;
         next = NULL; prev = NULL;}

     void addToAdjacents(int a1, int dontuse, double mil, string rd, string t){
         if(c==0){
             adjacents = new connections*[24];
        for(int i = 0; i<24; i++)
             adjacents[i] = new connections;
         }
         int d = c;
          adjacents[d] = new connections(a1,dontuse,mil,rd,t);
        dijDist = 10000000; visited = 0;
     }