#include?
#include?
#include?
#include?“hashMap.h“
#include?“ChainList.h“
#include?“minHeap.h“
using?namespace?std;


const?int?N?=?16;
const?int?M?=?N?*?（N?-?1）?/?2;


struct?Flight?{
	char?id[10]?start[20]?end[20];
	int?startTime?endTime;
	int?startID?endID;
	int?fee;
	Flight（
		const?char?*i
		const?char?*s
		const?char?*e
		int?st
		int?et
		int?f
		）?:?startTime（st）?endTime（et）?fee（f）
		startID（-1）?endID（-1）?{
		strcpy（id?i）;
		strcpy（start?s）;
		strcpy（end?e）;
	}
};

int?time（int?h?int?m）?{
	return?h?*?60?+?m;
}

Flight?flights[N]?=?{
	Flight（“6320“?“北京“?“上海“?time（16?20）?time（17?25）?680）
	Flight（“6320“?“上海“?“北京“?time（18?0）?time（19?5）?680）
	Flight（“2104“?“北京“?“烏魯木齊“?time（8?0）?time（9?55）?1150）
	Flight（“2104“?“烏魯木齊“?“北京“?time（10?45）?time（11?40）?1150）
	Flight（“201“?“北京“?“西安“?time（15?25）?time（17?0）?930）
	Flight（“201“?“西安“?“北京“?time（12?35）?time（14?15）?930）
	Flight（“2323“?“西安“?“廣州“?time（7?15）?time（9?35）?1320）
	Flight（“2323“?“廣州“?“西安“?time（10?15）?time（11?35）?1320）
	Flight（“173“?“拉薩“?“昆明“?time（10?20）?time（11?45）?830）
	Flight（“173“?“昆明“?“拉薩“?time（12?35）?time（14?0）?830）
	Flight（“3304“?“拉薩“?“武漢“?time（14?15）?time（15?45）?890）
	Flight（“3304“?“武漢“?“拉薩“?time（16?25）?time（17?55）?890）
	Flight（“82“?“烏魯木齊“?“昆明“?time（9?30）?time（12?15）?1480）
	Flight（“82“?“昆明“?“烏魯木齊“?time（13?5）?time（15?50）?1480）
	Flight（“4723“?“武漢“?“廣州“?time（7?5）?time（8?45）?810）
	Flight（“4723“?“廣州“?“武漢“?time（11?25）?time（13?5）?810）
};


HashMap?map（hashf?equalf）;
char?cityID[N][30];

char?startCity[30]?endCity[30];
char?method;?//?a:?min?time;?b:?min?fee;?c:?min?trans

ChainList?G[N];
int?m?=?0;

int?d[N];
int?path[N];
MinHeap?>?heap;




void?mapCities（）?{
	for?（int?i?=?0?j?=?0;?i?		if?（map.insert（flights[i].start?j））?{
			strcpy（cityID[j]?flights[i].start）;
			++j;
		}
		if?（map.insert（flights[i].end?j））?{
			strcpy（cityID[j]?flights[i].end）;
			++j;
		}
	}

	for?（int?i?=?0?j?=?0;?i?		flights[i].startID?=?*map.find（flights[i].start）;
		flights[i].endID?=?*map.find（flights[i].end）;
	}
}

//?Build?Graph
void?buildGraph（）?{
	for?（int?i?=?0;?i?		G[flights[i].startID].insert（i）;
	}
}


bool?each（int?&i）?{
	Flight?flight?=?flights[i];
	int?u?=?flight.startID;
	int?v?=?flight.endID;
	
	switch?（method）?{
	case?‘a(chǎn)‘:
	{
			??if?（d[v]?==?-1?||?d[v]?>?d[u]?+?flight.endTime?-?flight.startTime）?{
				??d[v]?=?d[u]?+?flight.endTime?-?flight.startTime;
				??path[v]?=?u;
				??heap.insert（make_pair（d[v]?v））;
			??}
	}
		break;
	case?‘b‘:
	{
			??if?（d[v]?==?-1?||?d[v]?>?d[u]?+?flight.fee）?{
				??d[v]?=?d[u]?+?flight.fee;
				??path[v]?=?u;
				??heap.insert（make_pair（d[v]?v））;
			??}
	}
		break;
	case?‘c‘:
	{
			??if?（d[v]?==?-1?||?d[v]?

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????文件?????????873??2016-06-08?21:08??全國(guó)交通咨詢模擬.txt
?????目錄???????????0??2016-06-08?21:06??第八章\
?????目錄???????????0??2016-01-02?22:50??第八章\Debug\
?????文件???????88064??2016-06-08?21:06??第八章\Debug\第八章.exe
?????文件??????487460??2016-06-08?21:06??第八章\Debug\第八章.ilk
?????文件?????1084416??2016-06-08?21:06??第八章\Debug\第八章.pdb
?????目錄???????????0??2016-01-02?22:50??第八章\第八章\
?????文件?????7143424??2016-06-08?21:06??第八章\第八章.sdf
?????文件?????????973??2016-01-02?21:20??第八章\第八章.sln
?????文件???????24576??2016-06-08?21:06??第八章\第八章.v12.suo
?????文件????????2923??2016-01-02?22:30??第八章\第八章\chainlist.h
?????目錄???????????0??2016-06-08?21:06??第八章\第八章\Debug\
?????文件??????226700??2016-06-08?21:06??第八章\第八章\Debug\main.obj
?????文件??????453632??2016-06-08?21:06??第八章\第八章\Debug\vc120.idb
?????文件??????356352??2016-06-08?21:06??第八章\第八章\Debug\vc120.pdb
?????文件????????1880??2016-06-08?21:06??第八章\第八章\Debug\第八章.log
?????目錄???????????0??2016-06-08?21:06??第八章\第八章\Debug\第八章.tlog\
?????文件????????1234??2016-06-08?21:06??第八章\第八章\Debug\第八章.tlog\cl.command.1.tlog
?????文件???????17134??2016-06-08?21:06??第八章\第八章\Debug\第八章.tlog\CL.read.1.tlog
?????文件?????????926??2016-06-08?21:06??第八章\第八章\Debug\第八章.tlog\CL.write.1.tlog
?????文件????????2190??2016-06-08?21:06??第八章\第八章\Debug\第八章.tlog\link.command.1.tlog
?????文件????????5032??2016-06-08?21:06??第八章\第八章\Debug\第八章.tlog\link.read.1.tlog
?????文件?????????882??2016-06-08?21:06??第八章\第八章\Debug\第八章.tlog\link.write.1.tlog
?????文件?????????260??2016-06-08?21:06??第八章\第八章\Debug\第八章.tlog\第八章.lastbuildstate
?????文件????????2203??2016-01-02?21:41??第八章\第八章\hashmap.h
?????文件????????4507??2016-01-02?22:30??第八章\第八章\main.cpp
?????文件????????1623??2016-01-02?21:41??第八章\第八章\minheap.h
?????文件????????3635??2016-01-02?21:43??第八章\第八章\第八章.vcxproj
?????文件????????1245??2016-01-02?21:41??第八章\第八章\第八章.vcxproj.filters