123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462 |
- /** 注:步行速度为90m/min **/
- #include <iostream>
- #include <stdio.h>
- #include <string.h>
- #include <iomanip>
- #include <stdlib.h>
- #include <math.h>
- #define INFINITY 65535 ///无穷大,即不相邻
- #define MAX_VERTEX_NUM 20 ///最大的顶点个数
- using namespace std;
- typedef int VRType;
- typedef char InfoType;
- typedef struct
- {
- int num;
- char name[20];
- char introduce[100];
- } VertexType;
- typedef struct ArcCell
- {
- VRType adj; ///距离
- InfoType *info;///边的信息
- } ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
- typedef struct
- {
- VertexType vex[MAX_VERTEX_NUM];///顶点向量
- AdjMatrix arcs; ///邻接矩阵
- int vexnum,arcnum; ///顶点数和边数
- } MGraph;
- VertexType site[11]=
- {
- {1,"生活区"," 一大群孩子的老巢"},
- {2,"球场"," 锻炼身体、休闲娱乐的地方"},
- {3,"风雨操场","情侣们秀恩爱的最佳去处"},
- {4,"众创空间","集合广播台等高大尚的工作的地方"},
- {5,"学苑超市","一个坑钱的地方,thing贼贵"},
- {6,"浴室"," 让你出淤泥而不染的地方"},
- {7,"知味园"," 小而拥挤、人流量te多还难吃的就餐地方"},
- {8,"致知楼"," 结合上课和办公与一体的高端教学楼"},
- {9,"敏行楼"," 夏天不热、冬天不冷的实验楼,也是报告厅所在地"},
- {10,"图书馆"," 还在建设中,想进去都进不去"},
- {11,"学校南门","学校正门,学校的门面,然而基本没开过"}
- };
- void schoolmap();///学校地图
- void menu();///菜单
- void create(MGraph &g,VertexType site[]);///创建邻接矩阵
- void output(MGraph g,int i);///根据序号i输出对应的地点的相关信息
- void search(MGraph g);///查找某个地点信息
- void Shortest_Path_Dijkstra(MGraph g,int v0,int P[][20],int D[20]);///Dijkstra算法
- void ShortestPath_FLOYD(MGraph g, int P[20][20][20], int D[][20]);///FLOYD算法
- void add_arc(MGraph &g);///增加修改地点间路径
- void delete_arc(MGraph &g);///删除某一条边
- void display_num(MGraph g);///显示所有地点序号名称
- void display_all(MGraph g);///输出具体信息
- void update(MGraph &g);///修改某一个地点信息
- int main()
- {
- int v1,v2,P1[20][20],P2[20][20][20],D1[20],D2[20][20],i,j,k;
- MGraph g;
- create(g,site);
- printf(" 欢迎来到安科地图导航! \n");
- LL1:
- menu();
- printf("please intput your choose:");
- scanf("%d",&i);
- switch(i)
- {
- case 0:
- schoolmap();
- goto LL1;
- break;
- case 1:
- display_num(g);
- goto LL1;
- break;
- case 2:
- display_all(g);
- goto LL1;
- break;
- case 3:
- search(g);
- goto LL1;
- break;
- case 4:
- printf("请输入地点的序号:\n");
- scanf("%d",&k);
- Shortest_Path_Dijkstra(g,k-1,P1,D1);
- for(i=1; i<g.vexnum; i++)
- {
- printf("%d号(%s)到%d号(%s):",k,g.vex[k-1].name,i+1,g.vex[i].name);
- for(j=0; P1[i][j]!=-1; j++)
- printf("%d号(%s) ",P1[i][j]+1,g.vex[P1[i][j]].name);
- printf("\n距离为:%d\n",D1[i]);
- puts("");
- }
- goto LL1;
- break;
- case 6:
- ShortestPath_FLOYD(g,P2,D2);
- for(i=0; i<g.vexnum; i++)
- {
- for(int j=0; j<g.vexnum; j++)
- {
- if(i!=j)
- {
- if(D2[i][j]!=INFINITY)
- {
- cout<<g.vex[i].name<<"到"<<g.vex[j].name<<"的最短时间为:"<<setw(5)<<D2[i][j]/90<<"min"<<", 最短路径为:";
- for(int k=0; k<g.vexnum; k++)
- {
- if(P2[i][j][k]!=-1)
- cout<<g.vex[P2[i][j][k]].name<<" ";
- else
- break;
- }
- puts("");
- }
- else
- cout<<g.vex[i].name<<"到"<<g.vex[j].name<<"不可达"<<endl;
- }
- }
- puts("");
- }
- goto LL1;
- break;
- case 5:
- ShortestPath_FLOYD(g,P2,D2);
- for(i=0; i<g.vexnum; i++)
- {
- for(int j=0; j<g.vexnum; j++)
- {
- if(i!=j)
- {
- if(D2[i][j]!=INFINITY)
- {
- cout<<g.vex[i].name<<"到"<<g.vex[j].name<<"的最短长度为:"<<setw(5)<<D2[i][j]<<", 最短路径为:";
- for(int k=0; k<g.vexnum; k++)
- {
- if(P2[i][j][k]!=-1)
- cout<<g.vex[P2[i][j][k]].name<<" ";
- else
- break;
- }
- puts("");
- }
- else
- cout<<g.vex[i].name<<"到"<<g.vex[j].name<<"不可达"<<endl;
- }
- }
- puts("");
- }
- goto LL1;
- break;
- case 7:
- add_arc(g);
- goto LL1;
- break;
- case 8:
- delete_arc(g);
- goto LL1;
- break;
- case 9:
- update(g);
- goto LL1;
- break;
- case 10:
- printf("下次再来玩呦,嘤嘤嘤^_^!\n");
- exit(0);
- goto LL1;
- break;
- default:
- printf("你的输入有误,请重新输入!嘤嘤嘤qwq\n");
- goto LL1;
- break;
- }
- return 0;
- }
- void menu()
- {
- printf("************************************************************\n");
- printf("************************************************************\n");
- printf("*** 0.大安科全景地图 ***\n");
- printf("*** 1.显示所有地点的序号 ***\n");
- printf("*** 2.查询所有地点的信息 ***\n");
- printf("*** 3.查询某个地点的具体信息 ***\n");
- printf("*** 4.查询某个地点到其他地点的最短路径 ***\n");
- printf("*** 5.输出任意两个地点之间的最短路径 ***\n");
- printf("*** 6.输出任意两个地点之间的最短时间 ***\n");
- printf("*** 7.增加某一条边 ***\n");
- printf("*** 8.删除某一条边 ***\n");
- printf("*** 9.修改某个地点的具体信息 ***\n");
- printf("*** 10.退出系统 ***\n");
- printf("************************************************************\n");
- printf("************************************************************\n");
- }
- void schoolmap()
- {
- printf(" 安科平面图 \n");
- printf(" *----------------------------------------------------------------------------*\n");
- printf(" | |西门| |\n");
- printf(" |----------------------------------------------------------------------------|\n");
- printf(" | *----------------* *-----------------* *--------------------------------* |\n");
- printf(" | | | | | | 生活区 (1) | |\n");
- printf(" | | 风 雨 | | | | *----* *----* *----* *----* | |\n");
- printf(" | | | | | | | 德 | | 德 | | 德 | | 德 | | |\n");
- printf(" | | 操 场 | | 球场 (2) | | | 馨 | | 馨 | | 馨 | | 馨 | | |\n");
- printf(" | | | | | | | 苑 | | 苑 | | 苑 | | 苑 | | |\n");
- printf(" | | (3) | | | | | 1 | | 2 | | 3 | | 4 | | |\n");
- printf(" | | | | | | *----* *----* *----* *----* | |\n");
- printf(" | *----------------* *-----------------* *--------------------------------* |\n");
- printf(" | *-----------------------* *----------* |\n");
- printf(" | | 间 | 市 | 室 | | *------* | |\n");
- printf(" | | 空 | 超 | | | | B | | |\n");
- printf(" | | 创 | 苑 | | | | 园 | | |\n");
- printf(" | | 众 | 学 | 浴 | | | | | |\n");
- printf(" | | (4)| (5) |(6)| | | 味 | | |\n");
- printf(" | *-----------------------* | | | | |\n");
- printf(" | *---------* | 知 | | |\n");
- printf(" | | *--------* | | |\n");
- printf(" | | | | | |\n");
- printf(" | | | 知味园A | | |\n");
- printf(" | *-----------------------------------* | | | | |\n");
- printf(" | | *--------* *--------* *-------* | | *---------------* | |\n");
- printf(" | | | | | | | | | | (7) | |\n");
- printf(" | | | A | | B | | C | | *--------------------* |\n");
- printf(" | | | 楼 | | 楼 | | 楼 | | |\n");
- printf(" | | | 知 | | 知 | | 知 | | |\n");
- printf(" | | | 致 | | 致 | | 致 | | |\n");
- printf(" | | | | | | | | | |\n");
- printf(" | | *--------* *--------* *-------* | |\n");
- printf(" |-----* | (8) | *----------* |\n");
- printf(" | 门 | *-----------------------------------* | | |\n");
- printf(" | (11)| | 馆 | |\n");
- printf(" | | | 书 | |\n");
- printf(" | 南 | | 图 | |\n");
- printf(" |-----* *-------------------------------------* | (10) | |\n");
- printf(" | | (9) | *----------* |\n");
- printf(" | | *--------* *--------* *-------* | |\n");
- printf(" | | | | | | | | | |\n");
- printf(" | | | A | | B | | C | | |\n");
- printf(" | | | 楼 | | 楼 | | 楼 | | |\n");
- printf(" | | | 行 | | 行 | | 行 | | |\n");
- printf(" | | | 敏 | | 敏 | | 敏 | | |\n");
- printf(" | | | | | | | | | |\n");
- printf(" | | *--------* *--------* *-------* | | 东 门 | |\n");
- printf(" *-------*-------------------------------------*-------*-----------*----------*\n");
- printf("\n");
- }
- void create(MGraph &g,VertexType site[])
- {
- int i,j;
- g.vexnum=11;
- g.arcnum=12;
- for(i=0; i<11; i++)
- g.vex[i]=site[i];
- for(i=0; i<g.vexnum; i++)
- for(j=0; j<g.vexnum; j++)
- g.arcs[i][j]= {INFINITY,NULL};
- g.arcs[0][1].adj=150;
- g.arcs[1][2].adj=100;
- g.arcs[2][3].adj=141;
- g.arcs[3][4].adj=30;
- g.arcs[4][5].adj=30;
- g.arcs[5][9].adj=300;
- g.arcs[5][10].adj=410;
- g.arcs[6][7].adj=210;
- g.arcs[6][9].adj=180;
- g.arcs[0][4].adj=160;
- g.arcs[0][7].adj=400;
- g.arcs[9][10].adj=310;
- g.arcs[7][8].adj=190;
- for(i=0; i<g.vexnum; i++)
- for(j=0; j<g.vexnum; j++)
- g.arcs[j][i].adj= g.arcs[i][j].adj;
- }
- void output(MGraph g,int i)
- {
- printf("地点序号:%d\n",i);
- printf("地点名称:%s\n",g.vex[i-1].name);
- printf("地点简介:%s\n",g.vex[i-1].introduce);
- }
- void search(MGraph g)
- {
- int i;
- printf("请输入你想查找地点的序号:");
- scanf("%d",&i);
- output(g,i);
- }
- void Shortest_Path_Dijkstra(MGraph g,int v0,int P[][20],int D[20])
- {
- int v,w,i,j,final[20],min;
- for(v=0; v<g.vexnum; v++)
- {
- final[v]=0;
- D[v]=g.arcs[v0][v].adj;
- for(w=0; w<g.vexnum; w++)
- P[v][w]=-1;
- if(D[v]<INFINITY)
- {
- P[v][0]=v0;
- P[v][1]=v;
- }
- }
- D[v0]=0;
- final[v0]=1;
- for(i=1; i<g.vexnum; i++)
- {
- min=INFINITY;
- for(w=0; w<g.vexnum; w++)
- if(!final[w]&&D[w]<min)
- {
- v=w;
- min=D[w];
- }
- final[v]=1;
- for(w=0; w<g.vexnum; w++)
- if(!final[w]&&(min+g.arcs[v][w].adj<D[w]))
- {
- D[w]=min+g.arcs[v][w].adj;
- for(j=0; j<g.vexnum; j++)
- {
- P[w][j]=P[v][j];
- if(P[w][j]==-1)///在p[w][]第一个等于-1的地方加上顶点w
- {
- P[w][j]=w;
- break;
- }
- }
- }
- }
- }
- void ShortestPath_FLOYD(MGraph g, int P[20][20][20], int D[][20])
- {
- int u,v,w,i,j;
- for(v=0; v<g.vexnum; v++)
- for(w=0; w<g.vexnum; w++)
- {
- D[v][w]=g.arcs[v][w].adj;
- for(u=0; u<g.vexnum; u++)
- P[v][w][u]=-1;
- if(D[v][w]<INFINITY)
- {
- P[v][w][0]=v;
- P[v][w][1]=w;
- }
- }
- for(u=0; u<g.vexnum; u++)
- for(v=0; v<g.vexnum; v++)
- for(w=0; w<g.vexnum; w++)
- if(D[v][u]<INFINITY&&D[u][w]<INFINITY&&D[v][u]+D[u][w]<D[v][w])
- {
- ///更新D
- D[v][w]=D[v][u]+D[u][w];
- ///更新p,从v到w的路径是从v到u,再从u到w的所有路径
- for(i=0; i<g.vexnum; i++)
- {
- if(P[v][u][i]!=-1)
- P[v][w][i]=P[v][u][i];
- else
- break;
- }
- for(j=1; j<g.vexnum; j++) ///注意:这里j从1开始而不是从0开始,因为从v到u的路径最后一个顶点是u, 而从u到w的路径第一个顶点是u,只需打印u一次即可。
- {
- if(P[u][w][j]!=-1)
- P[v][w][i++]=P[u][w][j];
- else
- break;
- }
- }
- }
- void update(MGraph &g)
- {
- int i;
- printf("请输入你想查找的地点的序号:");
- scanf("%d",&i);
- if(i>=1&&i<=11)
- {
- printf("请输入新的地点名称:");
- scanf("%s",g.vex[i-1].name);
- printf("请输入新的地点名称简介:");
- scanf("%s",g.vex[i-1].introduce);
- }
- else printf("没有找到这个地方嘤嘤嘤qwq~\n");
- }
- void add_arc(MGraph &g)
- {
- int v1,v2,n;
- printf("请输入你想增加的边两端的顶点序号:");
- printf("请输入第一个顶点号:");
- scanf("%d",&v1);
- printf("请输入第二个顶点号:");
- scanf("%d",&v2);
- if(g.arcs[v1-1][v2-1].adj==INFINITY)
- {
- printf("请输入两点之间的距离:");
- scanf("%d",&g.arcs[v1-1][v2-1].adj);
- g.arcs[v2-1][v1-1].adj=g.arcs[v1-1][v2-1].adj;
- printf("增加成功!嘤嘤嘤^_^\n");
- }
- else
- {
- LL0:
- printf("这两点已经有路径存在了,你想要修改它吗?想的话请按1,不想请按2:\n");
- scanf("%d",&n);
- if(n==1)
- {
- printf("请输入两点之间的新的距离:");
- scanf("%d",&g.arcs[v1-1][v2-1].adj);
- g.arcs[v2-1][v1-1].adj=g.arcs[v1-1][v2-1].adj;
- printf("修改成功!嘤嘤嘤^-^\n");
- }
- else if(n==2)
- {
- printf("增加失败,嘤嘤嘤T_T\n");
- }
- else
- {
- printf("你的输入有误,请重新输入!嘤嘤嘤qwq\n");
- goto LL0;
- }
- }
- }
- void delete_arc(MGraph &g)
- {
- int v1,v2;
- printf("请输入你想删除的边两端的顶点序号:\n");
- printf("请输入第一个顶点号:\n");
- scanf("%d",&v1);
- printf("请输入第二个顶点号:\n");
- scanf("%d",&v2);
- if(g.arcs[v1-1][v2-1].adj!=INFINITY)
- {
- g.arcs[v1-1][v2-1].adj=g.arcs[v2-1][v1-1].adj=INFINITY;
- printf("删除成功!嘤嘤嘤^_^\n");
- }
- else
- printf("删除失败!这两个点之间本来就没有直接通路,你还删它干嘛?!嘤嘤嘤qwq\n");
- }
- void display_num(MGraph g)
- {
- int i;
- printf("<地点序号> <地点名称>\n");
- for(i=0; i<g.vexnum; i++)
- printf("%5d %s\n",g.vex[i].num,g.vex[i].name);
- }
- void display_all(MGraph g)
- {
- int i;
- printf("<地点序号> <地点名称> <地点简介>\n");
- for(i=0; i<g.vexnum; i++)
- {
- printf("%5d %s %s\n",g.vex[i].num,g.vex[i].name,g.vex[i].introduce);
- }
- }
|