railsystem.cpp

SSD6卡耐基梅陇大学OP7答案 绝对正确 SSD6数据结构 是一门很重要的课程 希望对大家有帮助

#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

	map<string, City*>::iterator it = cities.begin();

	for (;it != cities.end(); it++) {

		it->second->visited = false;
		it->second->total_fee = INT_MAX;
		it->second->total_distance = INT_MAX;
		it->second->from_city = "";
	}   
}

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() ) {
		
			// TODO: Add entries in the cities container and
			// and services in the rail system for the new 
            // cities we read in.

			if ( cities.find(from) == cities.end() ) {
				cities[from] = new City(from);
			}
			Service* sp = new Service(to,fee,distance);
			outgoing_services[from].push_back(sp);

		}
	}

	inf.close();
}

RailSystem::~RailSystem(void) {

    // TODO: release all the City* and Service*
    // from cities and outgoing_services

	map<string, City*>::iterator it = cities.begin();
	
	for ( ; it != cities.end() ; it++) {
		delete it->second;
	}

	map<string, list<Service*> >::iterator it1 = outgoing_services.begin();

	for ( ; it1 != outgoing_services.end() ; it1++) {

		list<Service*>::iterator it2 = (it1->second).begin();

		for ( ; it2 != (it1->second).end() ; it2++) {
			delete *it2;
		}
	}

}

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
    

	// Return the total fee and total distance.
	// Return (INT_MAX, INT_MAX) if not path is found.
	if (cities[to]->visited) {
		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 c = city;
	string path = cities[city]->name;

	while (cities[c]->from_city != cities[c]->name) {
	
		path = cities[c]->from_city + " to " + path;
		c = cities[c]->from_city;
	}

	return path;
}