/* Subject: Contest submission for problem #3, file 3.cc */ /* cyc@imail.EECS.Berkeley.EDU */ /* Wed Sep 17 20:52:56 PDT 2003 */ /*___CONTEST_SUBMISSION___ cyc 3 */ // CS198, Assignment 3, Problem 3 // By Chris Crutchfield // Begun: 5:20 PM // Ended: 7:52 PM // Time: 2 Hours, 32 Minutes #include #include #include using namespace std; struct destination { int address, distance; destination(int add, int dis); }; destination::destination(int add, int dis) { address = add; distance = dis; } struct room { vector passages; void add_passage(int add, int dis) { destination *tmp = new destination(add, dis); passages.push_back(tmp); }; }; void connect_rooms(vector &rooms) { int add1, add2, dis; cin >> add1 >> add2 >> dis; rooms[add1].add_passage(add2, dis); rooms[add2].add_passage(add1, dis); } bool member(destination *key, vector &path) { for(int i = 0; i < path.size(); i++) if(key->address == path[i]->address) return true; return false; } vector tie_breaker(vector &path1, vector &path2) { int i = 0; while(true) { if(path1.size() <= i) return path2; if(path2.size() <= i) return path1; if(path1[i]->address < path2[i]->address) return path1; if(path1[i]->address > path2[i]->address) return path2; i++; } } int sum(vector &path) { int count = 0; if(path.size() == 0) count = 32768; for(int i = 0; i < path.size(); i++) count += path[i]->distance; return count; } vector best_path(vector > &lst) { vector result; if(lst.size() == 0) return result; int shortest = sum(lst[0]); result = lst[0]; int tmp; for(int i = 1; i < lst.size(); i++) { tmp = sum(lst[i]); if(tmp < shortest) { shortest = tmp; result = lst[i]; } if(tmp == shortest) result = tie_breaker(result, lst[i]); } return result; } vector find_shortest(const vector &rooms, vector path, int prev, int dest) { int where = path[path.size()-1]->address; vector tmp; vector > lst; if(where == dest) { return path; } for(int i = 0; i < rooms[where].passages.size(); i++) { if(!(member(rooms[where].passages[i], path)) && (prev != rooms[where].passages[i]->address)) { tmp = path; tmp.push_back(rooms[where].passages[i]); lst.push_back(find_shortest(rooms, tmp, where, dest)); } else { tmp.resize(1); tmp[0] = new destination(where, 32768); lst.push_back(tmp); } } return best_path(lst); } int main() { int size; bool eaten = false; vector rooms; vector shortest_path; vector snark_path; vector borogove_path; destination *tmp; cin >> size; rooms.resize(size); while(!cin.eof()) { connect_rooms(rooms); } tmp = new destination(1,0); shortest_path.push_back(tmp); shortest_path = find_shortest(rooms, shortest_path, -1, 0); tmp = new destination(2,0); for(int i = 1; i < shortest_path.size(); i++) { borogove_path.push_back(shortest_path[i]); snark_path.push_back(tmp); snark_path = find_shortest(rooms, snark_path, -1, shortest_path[i]->address); if(2*sum(snark_path) < sum(borogove_path)) eaten = true; snark_path.resize(0); } if(eaten) cout << "Snark eats" << endl; else cout << "Borogove escapes" << endl; exit(0); }