123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612 |
- #include<bits/stdc++.h>/** 注:步行速度为90m/min **/
- #include "stdio.h"
- #include "string.h"
- #include "windows.h"
- #define INFINITY 99999 ///无穷大,即不相邻
- #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; ///邻接矩阵#include<conio.h>
- 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);///修改某一个地点信息 /******/
- /******* *******/
- /*****************************************************************************************************************/
- /*****************************************************************************************************************/
- char reg_name[30]="",reg_pwd[10]="";
- char on_name[30],on_pwd[10];
- //用户注册系统
- void regist()
- {
- system("pause");//清屏
- system("cls");
- printf("\n\n\t\t\t欢迎使用安科地图导航注册系统\n\n");
- while(1)
- {
- //输入用户名
- printf("\t\t请输入用户名:");
- scanf("%s",reg_name);
- //判断用户名
- if(strlen(reg_name))
- {
- while(1)
- {
- //输入密码
- printf("\n\t\t请输入密码:");
- scanf("%s",reg_pwd);
- //判断密码
- if(strlen(reg_pwd))
- {
- printf("\n\n\t\t注册成功,您的用户名是%s,密码是%s\n\n",reg_name,reg_pwd);
- break;
- }
- else
- {
- printf("\n\t\t密码的长度为%d,请重新输入\n",strlen(reg_pwd));
- }
- }
- break;
- }
- else
- {
- printf("\n\t\t用户名的长度为%d,请重新输入\n\n",strlen(reg_name));
- }
- }
- }
- //判断是否注册
- int judge()
- {
- system("pause");//清屏
- system("cls");
- if(strcmp(reg_name,"")==0&&strcmp(reg_pwd,"")==0)
- {
- printf("\n\n\t\t您尚未注册,请先注册!\n\n");
- return 0;
- }
- else
- {
- return 1;
- }
- }
- //用户登录
- void dl()
- {
- int i;
- printf("\n\n\t\t\t欢迎使用安科地图导航登录系统\n\n");
- //三次登录验证
- for(i=1; i<=3; i++)
- {
- printf("\t\t请输入用户名:");
- scanf("%s",on_name);
- printf("\n\t\t请输入密 码:");
- scanf("%s",on_pwd);
- if(strcmp(reg_name,on_name)==0&&strcmp(reg_pwd,on_pwd)==0)
- {
- printf("\n\n\t\t登录成功,欢迎使用安科地图导航系统\n\n");
- break;
- }
- else
- {
- printf("\n\n\t\t登录失败,请重新登录\n\n");
- return dl();
- }
- }
- }
- 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);
- int id;
- while(1)
- {
- //输出界面
- printf("\n\n\t\t\t安科地图导航管理系统\n\n");
- printf("\t\t\t1:注册\n");
- printf("\t\t\t2:登录\n");
- printf("\t\t\t0:退出\n\n");
- //输入功能编号
- printf("\t\t请选择功能编号:");
- scanf("%d",&id);
- //判断
- switch(id)
- {
- case 1:
- regist();
- break;
- case 2:
- if(judge()==1)
- {
- dl();
- goto LL1;
- }
- break;
- case 0:
- printf("下次再来玩呦,嘤嘤嘤^_^!\n");
- exit(1);
- break;
- default:
- printf("\n\t\t您输入的功能编号有误,请重新输入!\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); for(int xx=0;xx<g.vexnum;xx++){
- for(int yy=0;yy<g.vexnum;yy++)
- printf("%7d",g.arcs[xx][yy]);
- printf("\n");
- }
- goto LL1;
- break;
- case 3:
- search(g);
- goto LL1;
- break;
- case 4:
- T: printf("请输入地点的序号:\n");
- scanf("%d",&k);
- if(k<1||k>11) {printf("不存在该地点!");goto T;}
- 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; for(int xx=0;xx<g.vexnum;xx++){
- for(int yy=0;yy<g.vexnum;yy++)
- printf("%7d",g.arcs[xx][yy]);
- printf("\n");
- }
- 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;for(int xx=0;xx<g.vexnum;xx++)
- 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);
- if(i<1||i>11)
- {printf("请重新输入!\n"); search(g);}
- else if(i<12)
- {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;
- }
- }
- for(int xx=0;xx<g.vexnum;xx++){
- for(int yy=0;yy<g.vexnum;yy++)
- printf("%7d",g.arcs[xx][yy]);
- printf("\n");
- }
- }
- 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);
- }
- }
|