4 #include <ext/hash_map>
6 using namespace __gnu_cxx;
9 inline int cost(std::string from, std::string to) const{
15 std::list<std::string> Bot::shortestPath(const std::string& from, PlayerType type, const Goal& goal, bool reverse) const{
16 return shortestPath(from, type, goal, SPCost(), reverse);
19 template<class Goal, class Cost>
20 std::list<std::string> Bot::shortestPath(const std::string& from, PlayerType type, const Goal& goal, const Cost& cost,bool reverse) const{
22 //cerr << "New shortest path from: " << from << endl;
24 priority_queue<SPInfo*, vector<SPInfo* >, SPInfoComp > pq;
25 hash_map<string,SPInfo> nodes;
27 SPInfo* node = &nodes[from];
29 node->settled = false;
35 bool hascar = type == cop_car;
47 front_insert_iterator<list<string> > ii(l);
55 //cerr << "Settled " << node->name << endl;
57 hash_map<string,Intersection>::const_iterator intersection = _intersections.find(node->name);
58 if (intersection == _intersections.end()){ //Sanity check, should never be true..
59 cerr << "BUG: Could not find intersection: " << node->name << endl;
62 for (hash_map<string,StreetType>::const_iterator street = intersection->second.connections.begin();
63 street != intersection->second.connections.end(); ++street){
64 hash_map<string,SPInfo>::iterator newNode = nodes.find(street->first);
65 bool travelStreet = false;
68 if (street->second != foot){
69 hash_map<string,Intersection>::const_iterator newInter = _intersections.find(street->first);
70 if (newInter != _intersections.end()){
71 hash_map<string,StreetType>::const_iterator st = newInter->second.connections.find(node->name);
72 if (st != newInter->second.connections.end())
73 travelStreet = st->second != foot;
78 travelStreet = street->second != foot;
80 travelStreet = street->second != car;
83 //cerr << "Adding street: " << street->first << endl;
84 if (newNode == nodes.end()){
85 n = &nodes[street->first];
86 n->name = street->first;
90 }else if (newNode->second.settled)
95 int c = cost.cost(node->name, n->name);
96 if (n->cost > node->cost + c){
97 n->cost = node->cost + c;
107 return list<string>();