#include <iostream> using namespace std; unsigend char weights[21][21]; int rows, cols;
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; }
bool DEBUG = true;
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; }
int main() { int east,south; cin >> east >> south; while (east!=0 and south!=0 ) { cin >> east >> south; } return 0; }
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; }
while (east!=0 and south!=0 ) { Reset(east,south); TestCoords(); cin >> east >> south; }
all: sol
void ReadGraph() { int r=0; int east = rows-1; for(r = 0; r <= east;r++) { ReadEastWest(r); if (r < east) { ReadNorthSouth(r); } } return; }
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; }
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; }
- 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
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; }