#define Number 20//最多景点数为20
#define Weight 999999//两景点边的权值
#include <iostream.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <process.h>
enum FT {False,True};//枚举类型默认情况下False=0,True=1
typedef struct
{
int distance;
}DIS;//任意两景点之间的距离信息
typedef struct
{
int numb; //每个景点的序号
char Name[20]; //每个景点的名称
char Info[100]; //每个景点的信息
}Data;//每一个景点的信息
typedef struct
{
int vexnum;
int arcnum;
Data vexs[Number];
DIS arcs[Number][Number];
}School;//校园信息
void CreatSchoolFace(School &CUG)
{
//初始化校园的各个景点和相关信息
CUG.vexnum=13;
CUG.arcnum=20;
int i;
for(i=0;i<CUG.vexnum;i++)CUG.vexs[i].numb=i;
//初始化顶点的信息
strcpy(CUG.vexs[0].Name,"北门");strcpy(CUG.vexs[0].Info,"通向北外的主要通道");
strcpy(CUG.vexs[1].Name,"北区食堂");strcpy(CUG.vexs[1].Info,"北区学生吃饭的地方");
strcpy(CUG.vexs[2].Name,"隧道");strcpy(CUG.vexs[2].Info,"地大独特的长为340米的地下通道，夏天里面很凉快");
strcpy(CUG.vexs[3].Name,"教三楼");strcpy(CUG.vexs[3].Info,"西区离体育馆较近的学生经常上课的地方。");
strcpy(CUG.vexs[4].Name,"体育馆");strcpy(CUG.vexs[4].Info,"主要是学生上体育课的地方");
strcpy(CUG.vexs[5].Name,"弘毅堂");strcpy(CUG.vexs[5].Info,"主要为学校举办各种文艺活动的地方");
strcpy(CUG.vexs[6].Name,"北区综合楼");strcpy(CUG.vexs[6].Info,"北区的教学楼");
strcpy(CUG.vexs[7].Name,"北区女生宿舍18#23#");strcpy(CUG.vexs[7].Info,"主要为地学院计算机学院外国语学院的女生住宿的地方");
strcpy(CUG.vexs[8].Name,"学生宿舍53栋"); strcpy(CUG.vexs[8].Info,"与西区篮球场紧挨着的男生宿舍");
strcpy(CUG.vexs[9].Name,"学三食堂"); strcpy(CUG.vexs[9].Info,"西区学生吃饭的地方");
strcpy(CUG.vexs[10].Name,"经管楼");strcpy(CUG.vexs[10].Info,"经管学院老师办公的地方");
strcpy(CUG.vexs[11].Name,"北一楼");strcpy(CUG.vexs[11].Info,"计算机学院老师办公的地方");
strcpy(CUG.vexs[12].Name,"教二楼");strcpy(CUG.vexs[12].Info,"传说发生过灵异事件，俗称鬼楼");
int ArcInfo[21][3]={
{0,1,300},{0,2,340},{0,11,350},{1,2,50},{1,7,250},{1,11,250},{2,3,500},{2,4,450},
{2,11,350},{2,7,400},{2,12,380},{4,12,300},{5,8,330},{5,9,100},{6,7,350},{6,10,90},
{7,11,280},{4,5,100},{3,4,80},{8,9,260},{10,11,90},
};
for (i=0;i<CUG.vexnum;i++)
for(int j=0;j<CUG.vexnum;j++)CUG.arcs[i][j].distance=Weight;
for (i=0;i<CUG.arcnum;i++)
{
int start=ArcInfo[i][0];
int end=ArcInfo[i][1];
CUG.arcs[start][end].distance=CUG.arcs[end][start].distance=ArcInfo[i][2];
}
return;
}
void DijKastra_ShortestPath(School CUG,int v0,int P[][Number],int D[])
{
//用狄克斯特拉算法求G的v0顶点到其余顶点v的最短路径P[v]及其带权路径长度D[v]
//若P[v][0]≠0,表明从源点出发存在一条到顶点v的最短路径，该路径存放在P[v]中
//final[v]为True则表明已经找到从v0到v的最短路径
int min,i,j,w,v;
FT final[Number];
for(v=0;v<CUG.vexnum;v++) //初始化
{ final[v]=False;
D[v]=CUG.arcs[v0][v].distance;
for(i=0;i<CUG.vexnum;i++)P[v][i]=0; //设空路径
}
D[v0]=0;
final[v0]=True; //初始时，v0属于S集 v0->v0 的最短路径为0且v0已经在v0->v0的路径中
//开始主循环，每次求得v0到某个顶点v的最短路径，并加v到S集
for(i=1;i<CUG.vexnum;i++) //寻找其余sh.vexnum-1个顶点
{
v=0; //从第一个定点0开始
min=Weight;
for(w=0;w <CUG.vexnum;w++) //寻找当前离U集点最近的顶点v
if((!final[w])&&(D[w] <min))
{
v=w;
min=D[w];
}
final[v]=True; //将v加入S集
for(j=0;P[v][j]!=False;j++); //若P[v][0]≠False,表明从源点出发存在一条到顶点v的最短路径 该路径存放在P[v]中
P[v][j]=v; //将路径P[v]延伸到顶点v
for(w=1;w<CUG.vexnum;w++) //更新当前最短路径及距离
if(!final[w]&&(min+CUG.arcs[v][w].distance <D[w]))
{
D[w]=min+CUG.arcs[v][w].distance;
for(j=0;P[v][j]!=False;j++)
P[w][j]=P[v][j];
}
}
}
void Print_ShortestPath(School CUG,int v0,int P[][Number],int D[],int Last)
{//显示从顶点u到其余顶点的最短路径及距离
int v,j;
cout<<"从"<<CUG.vexs[v0].Name<<"--->"<<CUG.vexs[Last].Name<<"的最短路径为 ："<<D[Last]<<"米"<<endl;
cout<<CUG.vexs[v0].Name;
for(j=0;P[Last][j]!=False;j++)
{
v=P[Last][j];//取路径上的对应代号
cout<<"->"<<CUG.vexs[v].Name;
}
cout<<endl;
}
void Print()
{
//打印出校园平面图
cout<<"\t\t中国地质大学（武汉）校园部分景点平面图如下"<<endl;
cout<<"注：从北综开始绘制的大致平面图"<<endl;
cout<<"\t 8 学生宿舍53栋"<<"\t 9 学三食堂"<<endl<<endl<<endl;
cout<<"\t\t 5弘毅堂"<<endl<<endl<<endl;
cout<<"\t 3 教三楼"<<"\t 4 体育馆 "<<"\t 12 教二楼 "<<endl<<endl;
cout<<"\t 2 隧道"<<endl<<endl<<endl;
cout<<"\t\t 1 北区食堂"<<"\t 7 北区女生宿舍18#23#"<<endl<<endl<<endl;
cout<<"\t 0 北门"<<"\t 11 北一楼"<<"\t10 经管楼（北四楼）"<<" 6 北区综合楼"<<endl<<endl<<endl;
}
void Modify(School *CUG)
{
int i;
char s[100];
cout<<"请输入要修改的景点的序号（0~12）：";
cin>>i;
if(i<0&&i>12)
{
cout<<"输入不合法！"<<endl;
return;
}/**/
cout<<"请将"<<i<<"景点信息内容: "<<CUG->vexs[i].Info<<"修改为："<<endl;
cin>>s;
strcpy(CUG->vexs[i].Info,s);
cout<<"改变之后"<<i<<"的景点信息为："<<CUG->vexs[i].Info<<endl;
return ;
}
void Find(School CUG)
{
int i;
Print();
cout<<"请输入你要查找的序号：";
cin>>i;
cout<<"您要查找的信息为："<<endl;
cout<<CUG.vexs[i].Name<<"\t"<<CUG.vexs[i].Info<<endl;
return;
}
void FindShort(School CUG)
{
int Start,End;
int P[Number][Number]; //存放从源点到各顶点的最短路径
int D[Number]; //存放从源点到各顶点的最短路径的距离
cout<<"请输入您要起点和终点:";
cin>>Start>>End;
DijKastra_ShortestPath(CUG ,Start, P,D);
Print_ShortestPath(CUG,Start,P,D,End);
}
void Face()
{
int i;
cout<<endl;
cout<<"\t 1 查看地图"<<endl
<<"\t 2 信息查询"<<endl
<<"\t 3 最短路径查询"<<endl
<<"\t 4 修改景点信息"<<endl
<<"\t 5 退出 "<<endl<<endl;
}
void main()
{
School CUG;
int Choose;
system("color 5f");
CreatSchoolFace(CUG);
Print();
while(Choose!=5)
{
Face();
cout<<"请选择（1~5）：";
cin>>Choose;
switch(Choose)
{
case 1:Print();break;
case 2:Find(CUG);break;
case 3:FindShort(CUG);break;
case 4:Modify(&CUG);break;
case 5:exit(0);
}
}
}
