/* Subject: Contest submission for problem #3, file 3.cc */ /* rob@imail.EECS.Berkeley.EDU */ /* Thu Sep 18 01:29:34 PDT 2003 */ /*___CONTEST_SUBMISSION___ rob 3 */ /* Assignment #3 Prob.3 - borogove and snark nickname: skyrob estimated time: 2 hr beginning time: 10:30 ending time: 1:30 actual time: 3 hr took longer becaue still not familiar with STL. */ #include #include #include #include #include #include using namespace std; struct node { int num; int dist; struct node* prev; bool visited; }; struct compare { bool operator()(const node n1, const node n2) const { if(n1.dist < n2.dist) return true; else if(n1.dist == n2.dist) { if(n1.num < n2.num) return true; else return false; } else return false; } }; set queue; vector path; int numRoom; void shortestPath(int, int, int[][1024], node[]); int main() { cin >> numRoom; int map[numRoom][1024]; int i, j; for(i = 0; i < numRoom; i++) { for(j = 0; j < numRoom; j++) { map[i][j] = -1; } } node list[numRoom]; for(i = 0; i < numRoom; i++) { list[i].num = i; list[i].dist = numeric_limits::max(); list[i].prev = NULL; list[i].visited = false; } int r1, r2, length; while(true) { if(cin.peek() == EOF) { break; } cin >> r1 >> r2 >> length; map[r1][r2] = length; map[r2][r1] = length; } shortestPath(1, 0, map, list); int n = 0; while(true) { node* temp = new node; temp->num = list[n].num; temp->dist = list[n].dist; temp->prev = list[n].prev; temp->visited = list[n].visited; path.push_back(*temp); if(list[n].prev == NULL || (list[n].prev)->num == 1) { break; } else { n = (list[n].prev)->num; } } /*vector::iterator test = path.begin(); while(test != path.end()) { cout << "room: " << (*test).num << " , dist: " << (*test).dist << endl; test++; }*/ while(!path.empty()) { for(i = 0; i < numRoom; i++) { list[i].dist = numeric_limits::max(); list[i].prev = NULL; list[i].visited = false; } node room = path.back(); shortestPath(2, room.num, map, list); if(list[room.num].dist < room.dist) { cout << "Snark eats\n"; exit(0); } path.pop_back(); } cout << "Borogove escapes\n"; exit(0); } void shortestPath(int sroom, int eroom, int map[][1024], node list[]) { list[sroom].dist = 0; list[sroom].visited = true; queue.insert(list[sroom]); int j, n; n = sroom; bool found = false; while(true) { for(j = 0; j < numRoom; j++) { if(map[n][j] != -1 && !list[j].visited) { if(list[j].dist > (list[n].dist + map[n][j])) { if(queue.find(list[j]) != queue.end()) { found = true; } if(found) queue.erase(list[j]); list[j].dist = list[n].dist + map[n][j]; list[j].prev = &(list[n]); if(j == eroom) { return; } queue.insert(list[j]); found = false; } } } queue.erase(list[n]); list[n].visited = true; if(queue.empty()) { break; } set::iterator iter = queue.begin(); n = (*iter).num; /* while(iter != queue.end()) { cout << "queue num: " << (*iter).num << " dist: " << (*iter).dist << endl; iter++; }*/ } }