範例程式碼 uva11336

//uva11336
#include <iostream>
#include <map>
#include <string>
#include <sstream>
#include <cstring>
#include <vector>

using namespace std;

map<string,int> nameTable;
map<int,string> nameTablei;
vector<pair<int,int>> roadList[2];
string mapName[2];
int oldmapN;

int getIdbyName(const string& name) {
	map<string,int>::iterator it = nameTable.find(name);
	if(it == nameTable.end())
		return -1;	
	return it -> second;
}

const string& getNamebyId(int id) {
	map<int,string>::iterator it = nameTablei.find(id);
	return it -> second;
}

int putName(const string& name) {
	int key = nameTable.size();
	nameTable.insert(pair<string, int>(name, key));
	nameTablei.insert(pair<int, string>(key, name));	
	return key;
}

void doCal();

int main(){
	string input;
	const int LOADMAP = 1;
	const int LOADSTREET = 2;
	int state = LOADMAP;
	int mapNo = 0;
	while(getline(cin,input)) {
		stringstream iss(input);
		if(state == LOADMAP){
			//Map name
			iss >> mapName[mapNo];
			if(mapNo == 0 && mapName[mapNo] == "END")
				return 0;
			state = LOADSTREET;
			continue;
		}
		
		if(strstr(input.c_str(),"* * *") != NULL){
			state = LOADMAP;
			if(mapNo == 1) {
				doCal();
				mapNo = 0;
				mapName[0].clear();
				mapName[1].clear();
				roadList[0].clear();
				roadList[1].clear();			
				nameTablei.clear();
				nameTable.clear();	
			}
			else {
				mapNo = 1;
				oldmapN = nameTable.size();
			}
			continue;
		}
		string place[2];	
		iss >> place[0] >> place[1];
		int placeId [2];
		for(int i = 0; i < 2; ++i) { //get PlaceID
			placeId[i] = getIdbyName(place[i]);
			if(placeId[i] == -1) {
				placeId[i] = putName(place[i]);
			}	
		}
		
		roadList[mapNo].push_back(pair<int, int>(placeId[0], placeId[1]));
	}

	return 0;
}

void doCal(){
	int martixSize = nameTable.size();
	
	int newMap[martixSize * martixSize];
	for(int i = 0; i < martixSize * martixSize; ++i) {
		newMap[i] = 0;	
	}

	for(int i = 0; i < roadList[1].size(); ++i) {
		int start = roadList[1][i].first, end = roadList[1][i].second ;
		newMap[start * martixSize + end] = newMap[end * martixSize + start] = 1;
	}
		
	for(int n = oldmapN; n < martixSize; ++n)
		for(int i = 0; i < martixSize; ++i)
			for(int j = 0; j < martixSize;++j)
				newMap[i * martixSize + j] |= newMap[i * martixSize + n] && newMap[n * martixSize + j];
	
	for(int i = 0; i < roadList[0].size(); ++i) {
		int start = roadList[0][i].first, end = roadList[0][i].second;
		if(newMap[(roadList[0][i].first) * martixSize + (roadList[0][i].second)] == 0 ) {
			//no route
			cout << "NO: " << mapName[1] << " is not a more detailed version of " << mapName[0] << "\n";
			return;
		}
	}
	
	cout << "YES: " << mapName[1] << " is a more detailed version of " << mapName[0] << "\n";
	return;
}