交通咨询模拟系统

一．问题描述 设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：（1）时间最短（2）费用最小（3）中转次数最少。 二、实验要求 （1）选取合适的数据结构存储带权路线图 （2）实现单源最短路径算法

#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 < N; ++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 < N; ++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 < N; ++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‘:
	{
			  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] 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件         873  2016-06-08 21:08  全国交通咨询模拟.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