南阳理工课程设计-校园导航
程序员文章站
2024-03-01 18:49:46
...
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
typedef long long LL;
const LL INF = 0x3f3f3f3f;
map<int,string>A;
struct Edge
{
int from, to; LL dist; //起点,终点,距离
Edge(int from, int to, LL dist):from(from), to(to), dist(dist) {}
};
struct Dijkstra
{
int n, m; //结点数,边数(包括反向弧)
vector<Edge> edges; //边表。edges[e]和edges[e^1]互为反向弧
vector<int> G[MAXN]; //邻接表，G[i][j]表示结点i的第j条边在edges数组中的序号
int vis[MAXN]; //标记数组
LL d[MAXN]; //s到各个点的最短路
int p[MAXN]; //上一条弧
void init(int n)
{
this->n = n;
edges.clear();
for (int i = 0; i <= n; i++) G[i].clear();
}
void AddEdge(int from, int to, int dist)
{
edges.push_back(Edge(from, to, dist));
m = edges.size();
G[from].push_back(m - 1);
}
struct HeapNode
{
int from; LL dist;
bool operator < (const HeapNode& rhs) const
{
return rhs.dist < dist;
}
HeapNode(int u, LL w): from(u), dist(w) {}
};
void dijkstra(int s)
{
priority_queue<HeapNode> Q;
for (int i = 0; i <= n; i++) d[i] = INF;
memset(vis, 0, sizeof(vis));
d[s] = 0;
Q.push(HeapNode(s, 0));
while (!Q.empty())
{
HeapNode x = Q.top(); Q.pop();
int u = x.from;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < G[u].size(); i++)
{
Edge& e = edges[G[u][i]];
if (d[e.to] > d[u] + e.dist)
{
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
Q.push(HeapNode(e.to, d[e.to]));
}
}
}
}
void output(int start,int end)
{
if (end == start)
{
cout<<A[end];
return ;
}
output(start,edges[p[end]].from);
cout<<"->"<<A[end];
}
}gao;
int map1[1009][1009];
void init1()
{
for(int i = 1 ;i <= 13;++i)
{
for(int j = 1;j <= 13;++j)
{
map1[i][j] = rand()%1000+10;
}
}
A[1] = "学校大门";A[2] = "领创空间中关村";A[3] = "老校区各教学楼";A[4] = "菜鸟驿站";A[5] = "梦溪湖";
A[6] = "汇森楼";A[7] = "图书馆";A[8] = "体育馆";A[9] = "田径场";A[10] = "餐厅";A[11] = "宿舍楼";A[12] = "开水房";A[13] = "齐贤广场";
}
void view()
{
printf("┏-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-* ┓\n");
puts("|1. 学校大门 学校的门面 |\n");
puts("|2. 领创空间中关村 英才聚集之地 |\n");
puts("|3. 老校区各教学楼 里面包含了几个学院 |\n");
puts("|4. 菜鸟驿站 同学们收发快递的地方 |\n");
puts("|5. 梦溪湖 学校里面的活水湖，水质良好，鱼虾成群 |\n");
puts("|6. 汇森楼 大学生创业的地方，雄伟壮观 |\n");
puts("|7. 图书馆 藏书丰富，环境优雅，同学们的备考必去之处 |\n");
puts("|8. 体育馆 是南工学子展现青春活力的地方，可容纳两千多名观众 |\n");
puts("|9. 田径场 塑胶跑道，看台，各届运动会举办的场地 |\n");
puts("|10. 餐厅 分为风味餐厅，民族餐厅还有大餐厅，物美价廉 |\n");
puts("|11. 宿舍楼 学生居住的地方，环境幽静，均配备空调，冬暖夏凉 |\n");
puts("|12. 开水房 免费提供开水 |\n");
puts("|13. 齐贤广场 学生们文艺活动的场所 |\n");
printf("┗-*-*_*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-* ┛\n");
printf("按数字键继续。。\n");
char t;
cin>>t;
}
void viewlu()
{
printf("┏-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-* ┓\n");
puts("|1. 学校大门 |\n");
puts("|2. 领创空间中关村 老校区各教学楼 |\n");
puts("|3. |\n");
puts("|4. 梦溪湖 |\n");
puts("|5. 汇森楼 |\n");
puts("|6. |\n");
puts("|7. 图书馆 齐贤广场 |\n");
puts("|8. |\n");
puts("|9. 体育馆 |\n");
puts("|10. |\n");
puts("|11. 田径场 |\n");
puts("|12. 餐厅 开水房 菜鸟驿站 |\n");
puts("|13. 宿舍楼 |\n");
printf("┗-*-*_*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-* ┛\n");
printf("按数字键继续。。\n");
char t;
cin>>t;
}
void print()
{
printf("\n 南阳理工学院校园导游图\n");
printf(" ┏ *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*┓\n");
printf(" * 1.浏览校园全景 * \n");
printf(" * 2.查看所有游览地 * \n");
printf(" * 3.选择出发点和目的地 * \n");
printf(" * 4.显示路径 * \n");
printf(" * 5.添加路径 * \n");
printf(" * 6.删除路径 * \n");
printf(" * 7.退出系统 * \n");
printf(" ┗ *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*┛\n");
printf("Option-->:");
}
void liangdicha()
{
gao.init(1000);
int u= 0;
for(int i = 1 ;i <= 13;++i)
{
for(int j = 1;j <= 13;++j)
{
if(i == j)
{
continue;
}
cout<<"从"<<A[i]<<"->"<<A[j]<<"的路乘是"<<map1[i][j]<<"，";putchar('\n');
gao.AddEdge(i,j,map1[i][j]);
}
}
putchar('\n');
printf("按数字键继续。。\n");
char t;
cin>>t;
}
void liangdicha1()
{
gao.init(1000);
int u= 0;
for(int i = 1 ;i <= 13;++i)
{
for(int j = 1;j <= 13;++j)
{
if(i == j)
{
continue;
}
gao.AddEdge(i,j,map1[i][j]);
}
}
}
void add()
{
int x,y,step;
printf("请输入两地的编号和路乘\n");
printf("请输入开始地编号\n");
cin>>x;
printf("请输入结束地编号\n");
cin>>y;
printf("请输入两地长度\n");
cin>>step;
map1[x][y] = min(map1[x][y],step);
printf("添加成功!\n");
printf("按数字键继续。。\n");
char t;
cin>>t;
}
void detele()
{
int x,y,step;
printf("请输入两地的编号\n");
printf("请输入开始地编号\n");
cin>>x;
printf("请输入结束地编号\n");
cin>>y;
map1[x][y] = INF;
printf("添加成功!\n");
printf("按数字键继续。。\n");
char t;
cin>>t;
}
void djs()
{
int a;int b;
for(int i = 1;i <= 13;++i)
{
cout<<i<<":";
cout<<A[i]<<endl;
}
liangdicha1();
puts("请选择开始地方编号\n");
cin>>a;
puts("请选择结束地方编号\n");
cin>>b;
gao.dijkstra(a);
cout<<"从"<<A[a]<<"到"<<A[b];
if(gao.d[b] == INF)
{
printf("无路\n");
}
else{
printf("最短路为%d\n",gao.d[b]);
}
puts("路径为：");
gao.output(a,b);
putchar('\n');
printf("按数字键继续。。\n");
char t;
cin>>t;
}
int main()
{
system("color e0");//设置调试窗口背景和字体颜色
init1();
while(1)
{
system("cls");
print();
int a;
cin>>a;
switch(a)
{
case 1:view();break;
case 2:viewlu();break;
case 3:djs();break;
case 4:liangdicha();break;
case 5:add();break;
case 6:detele();break;
case 7:return 0;break;
default:break;
}
}
return 0;
}实现图：
功能1：
功能2
、
功能3： 选择开始地点和结束地点输出路径
:
功能4：随机生成路径
功能5:添加路径
功能6;删除路径
功能7退出