• This appears to be a sparse graph.
• But I don't want the bookkeeping associated with a sparse graph.
• And the maximum number of nodes is 21x21 or 441
• In that case, the edge matrix would be at most 194,481 unsigned chars, so not too bad.
  • Distances are between speeds are between 0 and 9
  • A speed of 0 means you can not traverse the road.
• I am going to make the weigh matrix global, I don't want to pass it.
• I am also going to make the number of rows and columns global.

• #include <iostream>
  
  using namespace std;
  
  unsigend char weights[21][21];
  int rows, cols;
  

• Notice, we can treat this a two dimension array indexing in a one dimensional array.
• Vertex I is located at (i/cols, i%cols)
• Position (x,y) is at vertex x*cols+y
• I figure I will need to convert between these (and convince myself I have not made a mistake so)

• void NodeToPos(int node, int & x, int & y) {
     x = node /cols;
     y = node % cols;
     return;
  }
  
  int PosToNode(int x, int y) {
     return x*cols+y;
  }
  

• I would like to test this setup so I have written a test routine
  • I want to turn it off so I don't produce unnecessary output in the contest.
  • So I have a global DEBUG

  • bool DEBUG = true;
    	    

  • And a test routine for the two above functions

  • 
    void TestCoords() {
       int i, x,y;
    
       if (DEBUG) {
          for (i=0;i<rows*cols;i++) {
             NodeToPos(i,x,y);
             cout << i << " I is at (" << x << ", " << y << ")" << endl;
          }
    
          cout << endl;
          for(x = 0; x < rows; x++) {
             for(y=0;y<cols;y++) {
                cout <<  PosToNode(x,y) << " " ;
             }
             cout << endl;
          }
       }
       return;
    }
    	    

• so set up my initial main loop

• int main() {
     int east,south;
  
     cin >> east >> south;
     while (east!=0 and south!=0 ) {
        cin >> east >> south;
     }
  
     return 0;
  }
  

• Run this a few times to make sure I exit correctly.
• Then Add a routine to reset the graph given east and west

• void Reset(int east, int south) {
     rows = south + 1;
     cols = east + 1;
  
     for (int v1=0;v1<rows*cols;v1++) {
         for (int v2=0;v2<rows*cols;v2++) {
            weights[v1][v2] = '0';
         }
     }
  
     return;
  }
  

• And add this to main

•    while (east!=0 and south!=0 ) {
        Reset(east,south);
        TestCoords();
        cin >> east >> south;
     }
  

• all: sol
  

• Add a routine to read in a graph

• void ReadGraph() {
      int r=0;
      int east = rows-1;
      for(r = 0; r <= east;r++) {
         ReadEastWest(r);
         if (r < east) {
            ReadNorthSouth(r);
         }
      }
      return;
  }
  

• Reading east west connections

• void ReadEastWest(int r) {
      int c;
      unsigned char speed;
      char dir;
      for(c=0;c<cols-1;c++) {
         cin >> speed >> dir;
         switch(dir) {
            case '>':
                // note I will be going from (r,c) to (r,c+1)
                weights[PosToNode(r,c)][PosToNode(r,c+1) ] = speed;
                break;
            case '<':
                // note I will be going from (r,c+1) to (r,c)
                weights[PosToNode(r,c+1)][PosToNode(r,c) ] = speed;
                break;
            case '*':
                // both ways.
                weights[PosToNode(r,c+1)][PosToNode(r,c) ] = speed;
                weights[PosToNode(r,c)][PosToNode(r,c+1) ] = speed;
                break;
         }
      }
      return;
  }
  

• Note, NorthSouth is the same but rows and columns are switched.

void PrintEdge() {
     int v1, v2;

     if (DEBUG) {

         cout << "   ";
         for(v1=0;v1<rows*cols;v1++) {
            cout << setw(3) << v1 ;
         }
         cout << endl;

         for(v1=0;v1<rows*cols;v1++) {
             cout << setw(3) << v1 ;
             for(v2=0;v2<rows*cols;v2++) {
                if (weights[v1][v2] != '0' ) {
                       cout << setw(3) << weights[v1][v2];
                }else {
                     cout << setw(3) << " ";
                }
             }
             cout << endl;
         }
     }
     return;
}

• There is no way but to know this.
• I will not use a priority queue, so I will not be optimal.
• But I don't really need to be optimal, I need to get this done as quickly as possible.

 for each vertex
    vertex.price = infinity
    vertex.parent = null
    vertex.state = unexplored
 start.price=0
 start.state = active
 active.add(start)
 while not active.size() > 0 and destination.state != done
     current = active.remove_min()
     current.state = done
     for each node next adjacent to current
        if next.state != done
            if next.price > current.price+weight(current, next)
                next.price = current.price+weight(current, next)
                next.parent = current
            if next.state 

• See this demo

enum STATES {UNEXPLORED, ACTIVE, DONE};

const int INFIN =  2*23*2520;

struct nodeT{
    public:
    int price, parent;
    STATES state;
    nodeT() {
        parent = -1;
        state = UNEXPLORED;
        price = INFIN;
        return;
    }

};
void MoveMin(vector<nodeT> & nodes, vector<int> & active) {
   int tmp;
   int last = active.size()-1;
   for (int i=0;i<active.size();i++) {
       if (nodes[active[i]].price < nodes[active[last]].price) {
          tmp = active[i];
          active[i] = active[last];
          active[last] = tmp;

       }
   }
   return;
}

int Dijkstra() {
    vector<int> active;
    vector<nodeT> nodes(rows*cols);

    int current;
    int next;

    nodes[0].price = 0;
    nodes[0].state = ACTIVE;
    active.push_back(0);

    while (active.size() > 0 and nodes[rows*cols-1].state != DONE) {
        // extract the min;
        MoveMin(nodes, active);
        current = active.back();
        active.pop_back();

        nodes[current].state = DONE;

        for  (next =0; next < rows*cols; next++) {
           if (weights[current][next] > '0' and nodes[next].state != DONE) {
              int price = 2520/int(weights[current][next]-'0');
              if (nodes[next].price > nodes[current].price + price) {
                  nodes[next].price = nodes[current].price + price;
              }
              if (nodes[next].state ==  UNEXPLORED)  {
                  nodes[next].state = ACTIVE;
                  active.push_back(next);
              }
           }
        }
    }

    return nodes[rows*cols-1].price;
}
   

int main() {
   int east,south;
   int cost;

   cin >> south >> east;
   while (east!=0 and south!=0 ) {
      Reset(east,south);
      ReadGraph();
      PrintEdge();
      cost = Dijkstra();
      if (cost < INFIN) {
         cout << cost << " blips" << endl;
      } else {
         cout << "Holiday" << endl;
      }
      cin >> south >> east;
   }

   return 0;

}