用c++设计学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。 实现以下功能: (1)设计校园平面图,在校园景点选10个左右景点。以图中顶点表示校园内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等有关信息。 (2)为来访客人提供图中任意景点相关信息的查询。 (3)为来访客人提供任意景点的问路查询,即查询任意两个景点之间的一条最短路径。 要求:有合理提示;根据提示,可以完成相关的功能要求

时间: 2024-02-27 14:56:05 浏览: 22
这是一个典型的图论问题,可以使用Dijkstra算法或者Floyd算法来解决。以下是实现过程的示例代码: 景点类: ```c++ class Spot { public: string name; // 景点名称 int id; // 景点代号 string intro; // 景点简介 Spot(string _name, int _id, string _intro) : name(_name), id(_id), intro(_intro) {} }; ``` 边类: ```c++ class Edge { public: int from; // 起点 int to; // 终点 int dist; // 距离 Edge(int _from, int _to, int _dist) : from(_from), to(_to), dist(_dist) {} }; ``` 图类: ```c++ const int MAXN = 100; // 最大节点数 const int INF = 0x3f3f3f3f; // 无穷大 class Graph { public: vector<Spot> spots; // 存储所有景点 vector<Edge> edges; // 存储所有边 int G[MAXN][MAXN]; // 邻接矩阵 int n; // 节点数 int m; // 边数 int d[MAXN]; // 存储最短距离 int p[MAXN]; // 存储最短路径上的前驱节点 void addSpot(Spot s) { spots.push_back(s); n = spots.size(); } void addEdge(Edge e) { edges.push_back(e); m = edges.size(); G[e.from][e.to] = e.dist; } void init() { memset(G, INF, sizeof(G)); memset(d, INF, sizeof(d)); memset(p, -1, sizeof(p)); } void dijkstra(int s) { bool vis[MAXN] = {false}; d[s] = 0; for (int i = 0; i < n; i++) { int u = -1; int MIN = INF; for (int j = 0; j < n; j++) { if (!vis[j] && d[j] < MIN) { u = j; MIN = d[j]; } } if (u == -1) { return; } vis[u] = true; for (int v = 0; v < n; v++) { if (!vis[v] && G[u][v] != INF && d[u] + G[u][v] < d[v]) { d[v] = d[u] + G[u][v]; p[v] = u; } } } } void printPath(int s, int v) { if (v == s) { cout << spots[s].name; return; } printPath(s, p[v]); cout << " -> " << spots[v].name; } Graph() { init(); } }; ``` 使用示例: ```c++ int main() { Graph g; g.addSpot(Spot("教学楼A", 0, "这里是教学楼A")); g.addSpot(Spot("教学楼B", 1, "这里是教学楼B")); g.addSpot(Spot("教学楼C", 2, "这里是教学楼C")); g.addSpot(Spot("图书馆", 3, "这里是图书馆")); g.addSpot(Spot("体育馆", 4, "这里是体育馆")); g.addSpot(Spot("食堂", 5, "这里是食堂")); g.addSpot(Spot("宿舍楼A", 6, "这里是宿舍楼A")); g.addSpot(Spot("宿舍楼B", 7, "这里是宿舍楼B")); g.addSpot(Spot("宿舍楼C", 8, "这里是宿舍楼C")); g.addEdge(Edge(0, 1, 100)); g.addEdge(Edge(0, 2, 200)); g.addEdge(Edge(1, 2, 50)); g.addEdge(Edge(1, 3, 150)); g.addEdge(Edge(1, 5, 120)); g.addEdge(Edge(2, 3, 100)); g.addEdge(Edge(2, 5, 80)); g.addEdge(Edge(3, 4, 200)); g.addEdge(Edge(5, 6, 150)); g.addEdge(Edge(5, 7, 180)); g.addEdge(Edge(6, 8, 100)); g.addEdge(Edge(7, 8, 120)); int x, y; cout << "请输入起点和终点的代号:"; cin >> x >> y; g.dijkstra(x); cout << "从" << g.spots[x].name << "到" << g.spots[y].name << "的最短路径长度为:" << g.d[y] << endl; cout << "最短路径为:"; g.printPath(x, y); cout << endl; return 0; } ``` 用户界面可以在上述代码基础上添加交互逻辑,根据用户输入进行景点信息查询和问路查询。

相关推荐

最新推荐

recommend-type

C++实现两个有序数组的合并

主要为大家详细介绍了C++实现两个有序数组的合并,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
recommend-type

C++计算图任意两点间的所有路径

主要为大家详细介绍了C++求图任意两点间的所有路径,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
recommend-type

C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

主要介绍了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法,涉及C++二叉树的定义、遍历、统计相关操作技巧,需要的朋友可以参考下
recommend-type

C++学校人员信息管理系统课程设计.doc

一个用C++写的学校人员管理系统,适合大一大二的课程设计,里面运用到了链表、文件读写等一些C++基本语法操作
recommend-type

C++ 学生成绩管理系统设计报告书

个人课程设计报告书(内含源码) 内含4个类,各自具有其属性和行为。 基本实现了: (1)学生基本信息、考试科目及成绩的信息录入。 (2)已有学生信息的显示。 (3)学生基本信息的读取和保存输入数据等功能 (4)学生基本...
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

实现实时数据湖架构:Kafka与Hive集成

![实现实时数据湖架构:Kafka与Hive集成](https://img-blog.csdnimg.cn/img_convert/10eb2e6972b3b6086286fc64c0b3ee41.jpeg) # 1. 实时数据湖架构概述** 实时数据湖是一种现代数据管理架构,它允许企业以低延迟的方式收集、存储和处理大量数据。与传统数据仓库不同,实时数据湖不依赖于预先定义的模式,而是采用灵活的架构,可以处理各种数据类型和格式。这种架构为企业提供了以下优势: - **实时洞察:**实时数据湖允许企业访问最新的数据,从而做出更明智的决策。 - **数据民主化:**实时数据湖使各种利益相关者都可
recommend-type

用 Python 画一个可以动的爱心

好的,我可以帮助您使用Python来绘制一个动态的爱心。您可以使用turtle库来实现。以下是实现代码: ```python import turtle import math # 设置画布和画笔 canvas = turtle.Screen() canvas.bgcolor("black") pencil = turtle.Turtle() pencil.speed(0) pencil.color("red", "pink") pencil.pensize(3) # 定义爱心函数 def draw_love(heart_size, x_offset=0, y_offset=0):
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。