From Dusk Till Dawn/조현태

������������ ¶

~cpp
#include <iostream>
#include <vector>
#include <string>

using namespace std;

const char DEBUG_READ[] = "2\n3\nUlm Muenchen 17 2\nUlm Muenchen 19 12\nUlm Muenchen 5 2\nUlm Muenchen\n10\nLugoj Sibiu 12 6\nLugoj Sibiu 18 6\nLugoj Sibiu 24 5\nLugoj Medias 22 8\nLugoj Medias 18 8\nLugoj Reghin 17 4\nSibiu Reghin 19 9\nSibiu Medias 20 3\nReghin Medias 20 4\nReghin Bacau 24 6\nLugoj Bacau";

const int BUFFER_SIZE = 255;

#define TRUE 1
#define FALSE 0

struct STown
{
	STown(const char* inputName)
	{
		name = inputName;
	}
	string name;
	vector<STown*> nextTown;
	vector<int> startTime;
	vector<int> timeDelay;
};

vector<STown*> g_myTowns;
string g_suchStartTown;
string g_suchEndTown;
int g_minimumDelayTime = 0;

STown* SuchOrAddTown(const char* townName)
{
	for (register unsigned int i = 0; i < g_myTowns.size(); ++i)
	{
		if (g_myTowns[i]->name == townName)
			return g_myTowns[i];
	}
	g_myTowns.push_back(new STown(townName));
	return g_myTowns[g_myTowns.size() - 1];
}

const char* Parser(const char* readData)
{
	char startStationName[BUFFER_SIZE];
	char endStationName[BUFFER_SIZE];
	int startTime;
	int delayTime;
	int sizeOfTimeTable;

	sscanf(readData, "%d", &sizeOfTimeTable);
	readData = strchr(readData, '\n') + 1;
	for(register int i = 0; i < sizeOfTimeTable; ++i)
	{
		sscanf(readData, "%s %s %d %d", startStationName, endStationName, &startTime, &delayTime);

		STown* thisStation = SuchOrAddTown(startStationName);
		thisStation->nextTown.push_back(SuchOrAddTown(endStationName));
		thisStation->startTime.push_back(startTime % 24);
		thisStation->timeDelay.push_back(delayTime);
		
		readData = strchr(readData, '\n') + 1;
	}
	sscanf(readData, "%s %s", startStationName, endStationName);
	g_suchStartTown = startStationName;
	g_suchEndTown = endStationName;
	readData = strchr(readData, '\n');

	if (NULL != readData)
		return readData + 1;
	else
		return NULL;
}

bool isDeadTime(int inputTime)
{
	if (18 > inputTime % 24 && 6 < inputTime % 24)
		return TRUE;
	return FALSE;
}

void SuchTown(STown* startTown, STown* endTown)
{
	//// ������ ������ ////
	vector< vector<STown*> > allSuchList;
	vector<int> allDelay;
	vector<STown*> newTown;
	int newAddPoint;
	newTown.push_back(startTown);
	allDelay.push_back(0);
	allSuchList.push_back(newTown);

	do{
		//// ������ ��������� ������ ��������� ���해��� ��������� ���행합������. ////
		newAddPoint = allSuchList[0].size() - 1;
		STown* suchTown = allSuchList[0][allSuchList[0].size() - 1];
		for (register int i = 0; i < (int)(suchTown->nextTown.size()); ++i)
		{
			if (suchTown->timeDelay[i] <= 12 && !(isDeadTime(suchTown->startTime[i]) || isDeadTime(suchTown->startTime[i] + suchTown->timeDelay[i])))
			{
				vector<STown*> suchTownList = allSuchList[0];
				suchTownList.push_back(suchTown->nextTown[i]);
				allSuchList.push_back(suchTownList);
				
				if (allDelay[0] % 24 <= suchTown->startTime[i])
					allDelay.push_back(allDelay[0] + suchTown->startTime[i] - (allDelay[0] % 24) + suchTown->timeDelay[i]);
				else
					allDelay.push_back(allDelay[0] + (suchTown->startTime[i] + 24) - (allDelay[0] % 24) + suchTown->timeDelay[i]);

				if (g_suchEndTown == suchTown->nextTown[i]->name)
				{
					if ((0 != g_minimumDelayTime && g_minimumDelayTime > allDelay[allDelay.size() - 1]) || 0 == g_minimumDelayTime)
						g_minimumDelayTime = allDelay[allDelay.size() - 1];
				}
			}
		}
		allSuchList.erase(allSuchList.begin());
		allDelay.erase(allDelay.begin());
		//// ������한 ��������� ��������� ������ ��������� ������한 ������ ������합������. ////
		for (register int i = newAddPoint; i < (int)allSuchList.size(); ++i)
		{
			if (0 != g_minimumDelayTime && g_minimumDelayTime < allDelay[i])
			{
				allSuchList.erase(allSuchList.begin() + i);
				allDelay.erase(allDelay.begin() + i);
			}
			else
			{
				bool isSame = FALSE;
				for (register int j = 0; j < (int)allSuchList[i].size(); ++j)
				{
					for (register int k = j + 1; k < (int)allSuchList[i].size(); ++k)
					{
						if (allSuchList[i][j] == allSuchList[i][k])
						{
							allSuchList.erase(allSuchList.begin() + i);
							allDelay.erase(allDelay.begin() + i);
							--i;
							isSame = TRUE;
							break;
						}
					}
					if (isSame)
						break;
				}

			}
		}

		if (0 == allSuchList.size())
			break;
		//// ������ ��������� ������ ��������� ������ ��������� ���������. ////
		int minimumDelayPoint = 0;
		int minimumDelay = allDelay[0];
		for (register int i = 1; i < (int)allSuchList.size(); ++i)
		{
			if (minimumDelay > allDelay[i])
			{
				minimumDelay = allDelay[i];
				minimumDelayPoint = i;
			}
		}
		allDelay[minimumDelayPoint] = allDelay[0];
		vector<STown*> bufferSTown = allSuchList[minimumDelayPoint];
		allDelay[0] = minimumDelay;
		allSuchList[0] = bufferSTown;
	}while(0 != allSuchList.size());
}

void freeMemory()
{
	for (register int i = 0; i < (int)g_myTowns.size(); ++i)
		delete g_myTowns[i];
}

void main()
{
	int numberOfTestCase = 0;
	const char* readData = DEBUG_READ;
	sscanf(readData, "%d", &numberOfTestCase);
	readData = strchr(readData, '\n') + 1;
	for (register int i = 0; i < numberOfTestCase; ++i)
	{
		//// ������화 ////
		g_myTowns.clear();
		g_suchStartTown.clear();
		g_suchEndTown.clear();
		g_minimumDelayTime = 0;

		//// ������ ////
		readData = Parser(readData);
		SuchTown(SuchOrAddTown(g_suchStartTown.c_str()), SuchOrAddTown(g_suchEndTown.c_str()));
		freeMemory();
		if (0 == g_minimumDelayTime)
			cout << "There is no route Vladimir can take." << endl;
		else
			cout << "Vladimir needs " << g_minimumDelayTime / 24 << " litre(s) of blood. " << endl;
	}
}