复件 railsystem.cpp

ssd5op7 一个关于迪克斯拉算法的实现

#pragma warning (disable:4786)
#pragma warning (disable:4503)

#include "RailSystem.h"

void RailSystem::reset(void) {

    // TODO: reset the data objects of the 
    // City objects' contained in cities
	typedef map<string,City*> city_map;
	city_map::iterator i1 = cities.begin();
	city_map::iterator i2 = cities.end();
	while(i1 != i2){
		((*i1).second)->total_distance = 0;
		((*i1).second)->from_city = " ";
		((*i1).second)->total_fee = 0;
		i1 ++;
	}
    
}

RailSystem::RailSystem(string const &filename) {
    
    load_services(filename);
}

void RailSystem::load_services(string const &filename) {

	ifstream inf(filename.c_str());
	string from, to;
	int fee, distance;

	while ( inf.good() ) {
		// Read in the from city, to city, the fee, and distance.
		inf >> from >> to >> fee >> distance;
		if ( inf.good() ) {
			// Add entries in the cities container and
			// and services in the rail system for the new 
            // cities we read in.	
			if(!cities.count(from)){/*cout<<"Insert city from "<<from<<endl;*/
				cities.insert(map<string,City*>::value_type(from,new City(from)));
			}
			if(!cities.count(to))
				cities.insert(map<string,City*>::value_type(to,new City(to)));
			if(outgoing_services.count(from) == 0){
				outgoing_services.insert(map<string,list<Service*>>::value_type(from,list<Service*>()));
				outgoing_services[from].push_back(new Service(to,fee,distance));
			}
			else
				(outgoing_services[from]).push_back(new Service(to,fee,distance));
		}/*else
			cout<<"inf is in a wrong state!"<<endl;*/
	}

	inf.close();
}

RailSystem::~RailSystem(void) {
    // TODO: release all the City* and Service*
    // from cities and outgoing_services	
	typedef map<string,list<Service*>> tmap;
	tmap::iterator iter1 = outgoing_services.begin();
	tmap::iterator iter2 = outgoing_services.end();
	while(iter1 != iter2){
		list<Service*>::iterator it1 = (*iter1).second.begin();
		list<Service*>::iterator it2 = (*iter1).second.end();
		while (it1 != it2){
			delete *it1;
			it1 ++;
		}
		iter1++;
	}
	typedef map<string,City*> city_map;
	city_map::iterator i1 = cities.begin();
	city_map::iterator i2 = cities.end();
	while(i1 != i2){
		delete (*i1).second;
		i1 ++;
	}


}

void RailSystem::output_cheapest_route(const string& from,
                const string& to, ostream& out) {

	reset();
	pair<int, int> totals = calc_route(from, to);

	if (totals.first == INT_MAX) {
		out << "There is no route from " << from << " to " << to << "\n";
	} 
	else {
		out << "The cheapest route from " << from << " to " << to << "\n";
		out << "costs " << totals.first << " euros and spans " << totals.second
			<< " kilometers\n";
        cout << recover_route(to) << "\n\n";
	}
}

bool RailSystem::is_valid_city(const string& name) {

	return cities.count(name) == 1;
}

pair<int, int> RailSystem::calc_route(string from, string to) {

	priority_queue<City*, vector<City*>, Cheapest> candidates;
    // TODO: Implement Dijkstra's shortest path algorithm to
    // find the cheapest route between the cities
	City * pCity = cities[from];
	candidates.push(pCity);
	pCity->total_distance = 0;

	unsigned int citiesSeen = 0;
	for( ; citiesSeen < outgoing_services.size(); citiesSeen ++){
		do{
			if(candidates.empty())
				goto L;
			pCity = candidates.top();
			candidates.pop();
		} while(pCity->visited);
		pCity->visited = true;
		string cityName = pCity->name;
		Service* pService;
		list<Service*>::iterator it1 = outgoing_services[cityName].begin();
		list<Service*>::iterator it2 = outgoing_services[cityName].end();
		for(;it1 != it2;it1++){
			pService = (*it1);
			int fee = pService->fee;
			int distance = pService->distance;
			string cityTo = pService->destination;
			if(cities[cityTo]->total_fee == 0 || cities[cityTo]->total_fee > fee + pCity->total_fee){
				cities[cityTo]->total_fee = fee + pCity->total_fee;
				cities[cityTo]->total_distance = distance + pCity->total_distance;				
				cities[cityTo]->from_city = pCity->name;
				candidates.push(cities[cityTo]);
			}
		}
	}
	// Return the total fee and total distance.
	// Return (INT_MAX, INT_MAX) if not path is found.	
L:	if (cities[to]->visited){
		cities[from]->total_distance =0;
		return pair<int,int>(cities[to]->total_fee, cities[to]->total_distance);
	}else {
		return pair<int,int>(INT_MAX, INT_MAX);
 	}
}

string RailSystem::recover_route(const string& city) {
	
	// TODO: walk backwards through the cities
	// container to recover the route we found
	string str = "******";
	string tempCity = city;	
	while((cities[tempCity]->total_distance)!=0){
		str =  cities[tempCity]->name+" to "+str;
		tempCity = cities[tempCity]->from_city;
	}
	return tempCity+ " to "+str   ;
}