设计一个校园导游程序，为来学校的用户提供景点信息及路径查询服务。
① “景点信息查询”
系统为来访客人提供图中任意景点相关信息的查询功能。
用户选择该选项后，提示用户输入要查询的景点编号，根据景点编号显示出
该景点的名称和简介。
② “校门口到其他景点的路经查询”
系统为来访客人提供从校门口到图中任意景点的问路查询功能。
用户选择该选项后，提示用户输入要到达的景点编号，根据该景点编号显示
出从校门口到该景点的最短路径长度及路径信息（即路径上的顶点序列）
③ “校园各景点间的路经查询”
系统为为来访客人提供图中任意景点间的问路查询；
用户选择该选项后，提示用户输入起点编号及终点编号，根据起点和终点编
号确定起点到终点的最短路径及长度并直观显示。
①设计学校的校园平面图（有向图，任意两点间的去边和回边长度相等），
所含景点不少于 10 个，以图中顶点表示校内各景点，存放景点名称、代号、简
介等信息，以边表示路径，存放路径长度等相关信息。
②利用教材上建立图的邻接矩阵的算法实现图的存储。
③根据查找算法实现功能 1。
④根据迪杰斯特拉算法和教材上的参考程序实现功能 2。
⑤根据弗洛伊德算法和教材上的参考程序实现功能 3
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <setjmp.h>
using namespace std;
#define MaxInt 32767//表示正无穷
#define MVNum 100//最大顶点数
#define OK 1
#define ERROR -1
#define OVERFLOW -2
jmp_buf j;
typedef struct
{
char name[10];
char info[50];
}Place;
typedef int Status;
typedef Place VerTexType;
typedef int ArcType;
typedef struct
{
VerTexType vexs[MVNum];//顶点表
ArcType arcs[MVNum][MVNum];//邻接矩阵
int vexnum,arcnum;//图的当前点数和边数
}AMGraph;
typedef struct stack
{
int *base;
int *top;
int stacksize;
}SqStack;
int path[11][11];
int D[11][11];
bool isVisited[MaxInt];
SqStack S;
Status CreateUDN (AMGraph &G)//创建地图的邻接矩阵模型
{
G.vexnum = 11;
G.arcnum = 15;
strcpy(G.vexs[0].name,"正门");strcpy(G.vexs[0].info,"学校的正门。校训：博学深思，参天尽物");
strcpy(G.vexs[1].name,"主楼");strcpy(G.vexs[1].info,"学校的行政办公中心");
strcpy(G.vexs[2].name,"二号楼");strcpy(G.vexs[2].info,"二号楼，学校教学场所，外语学院的教学楼。");
strcpy(G.vexs[3].name,"外事三号楼");strcpy(G.vexs[3].info,"有关出国留学事务的咨询办公楼");
strcpy(G.vexs[4].name,"联通广场");strcpy(G.vexs[4].info,"标准化跑道，适宜锻炼身体的场所");
strcpy(G.vexs[5].name,"一号楼");strcpy(G.vexs[5].info,"一号楼，学校的机房教学楼之一，有七十年左右的历史");
strcpy(G.vexs[6].name,"图书馆");strcpy(G.vexs[6].info,"藏书丰富，设施良好，知识的摇篮");
strcpy(G.vexs[7].name,"汇文楼");strcpy(G.vexs[7].info,"学校的主要教学楼，承载黑大学子的梦想");
strcpy(G.vexs[8].name,"实验楼");strcpy(G.vexs[8].info,"雅思考试考场之一，标准化机房。");
strcpy(G.vexs[9].name,"四号楼");strcpy(G.vexs[9].info,"计算机学院、创业教育学院");
strcpy(G.vexs[10].name,"三号楼");strcpy(G.vexs[10].info,"C区主要教学楼");
for(int i = 0;i<G.vexnum;i++)
cout<<G.vexs[i].name<<endl;
for(int i = 0;i<G.vexnum;i++)//初始化邻接矩阵使边的权值均为MAXINT
for(int j = 0;j<G.vexnum;j++)
G.arcs[i][j] = MaxInt;
G.arcs[0][1] = 50;G.arcs[0][3] = 150;
G.arcs[1][2] = 20;G.arcs[1][3] = 50;
G.arcs[2][3] = 160;G.arcs[2][4] = 60;
G.arcs[3][6] = 300;G.arcs[4][5] = 100;
G.arcs[5][6] = 200;G.arcs[5][7] = 350;
G.arcs[6][8] = 180;G.arcs[7][8] = 240;
G.arcs[7][9] = 550;G.arcs[8][10] = 450;
G.arcs[9][10] = 50;
G.arcs[1][0] = 50;G.arcs[3][0] = 150;
G.arcs[2][1] = 20;G.arcs[3][1] = 50;
G.arcs[3][2] = 160;G.arcs[4][2] = 60;
G.arcs[6][3] = 300;G.arcs[5][4] = 100;
G.arcs[6][5] = 200;G.arcs[7][5] = 350;
G.arcs[8][6] = 180;G.arcs[8][7] = 240;
G.arcs[9][7] = 550;G.arcs[10][8] = 450;
G.arcs[10][9] = 50;
for(int i = 0;i<G.vexnum ;i++)
{
G.arcs[i][i]=0;
}
for(int i =0;i<G.vexnum;i++)
{
for(int j = 0;j<G.vexnum;j++)
{
cout<<"\t"<<G.arcs[i][j];
}
cout<<endl;
}
return OK;
}
Status InitStack (SqStack &S)
{
S.base = new int;
if(!S.base)cout<<"ERROR";
S.top = S.base;
S.stacksize = 100;
return OK;
}
Status Push(SqStack &S,int e)
{
if(S.top - S.base == S.stacksize)return ERROR;
*S.top++ = e;
return OK;
}
Status Pop(SqStack &S,int &e)
{
if(S.top == S.base)return 0;
int *temp;
temp = S.top;
S.top--;
delete temp;
e = *S.top;
return OK;
}
void ShowStack(SqStack &S)
{
int *top = S.top;
while(S.base != top)
{
cout<<(*(top-1))<<" ";
top--;
}
cout<<"over "<<endl;
}
int GetIndex(AMGraph &G,VerTexType v)
{
int index = -1;
for(int i=0;i<G.vexnum;i++)
{
if(v.name == G.vexs[i].name){return i;}//获取v1下标
}
return index;
}
void ShowInfo(AMGraph &G)
{
int choice;
cout<<"请输入你要查询的地点序号：";cin>>choice;
cout<<G.vexs[choice].info<<endl;
return;
}
void ShortertPath_Floyd(AMGraph &G)
{
for(int i = 0;i<G.vexnum;i++)
{
for(int j = 0;j<G.vexnum;j++)
{
D[i][j] = G.arcs[i][j];
if((D[i][j]<MaxInt)&&(i!=j))path[i][j]=i;
else path[i][j] = -1;
}
}
for(int k = 0;k<G.vexnum;++k)
{
for(int i = 0;i<G.vexnum;++i)
{
for(int j = 0;j<G.vexnum ;++j)
{
if(D[i][k]+D[k][j]<D[i][j])
{
D[i][j] = D[i][k]+D[k][j];
path[i][j] = path[k][j];
}
}
}
}
cout<<"path"<<endl;
for(int i = 0;i<G.vexnum;i++)
{
for(int j = 0;j<G.vexnum;j++)
{
cout<<"\t"<<path[i][j];
}
cout<<endl;
}
cout<<"D:"<<endl;
for(int i = 0;i<G.vexnum;i++)
{
for(int j = 0;j<G.vexnum;j++)
{
cout<<"\t"<<D[i][j];
}cout<<endl;
}
// for(int i = 0;i<G.vexnum ;i++)
// {
// for(int j = 0;j<G.vexnum;j++)
// cout<<D[i][j]<<"\t";
// cout<<endl;
// }
}
void Road(AMGraph &G,int v1,int v2)
{
int temp = v2;
do{
Push(S,temp);
temp = path[v1][temp];
}while(*(S.top-1)!=v1);
ShowStack(S);
InitStack(S);
}
int main()
{
//邻接矩阵部分
AMGraph G;
InitStack(S);
CreateUDN(G);
ShortertPath_Floyd(G);
cout<<endl;
while(1)
{system("cls");
cout<<"****************************************************************"<<endl;
cout<<"* 黑龙江大学校园导游系统 *"<<endl;
cout<<"* 1、景点信息查询 *"<<endl;
cout<<"* 2、校门口到其他景点的路经查询（单源最短路径） *"<<endl;
cout<<"* 3、校园各景点间的路经查询（各顶点对间最短路径） *"<<endl;
cout<<"****************************************************************"<<endl;
cout<<"请输入你的选项：";
int choice;
cin>>choice;
if(choice == 1)
{
ShowInfo(G);
getchar();
getchar();
}else if(choice == 2)
{
cout<<"请输入你要去哪里：";
int aim;
cin>>aim;
Road(G,0,aim);
getchar();
getchar();
}else if(choice == 3)
{
int from;
cout<<"请输入你要从哪里出发：";
cin>>from;
cout<<"请输入你要去哪里：";
int aim;
cin>>aim;
Road(G,from,aim);
getchar();
getchar();
}
else{
cout<<"输入错误，请重试"<<endl;
getchar();
getchar();
}
}
return 0;
}