用c++代码写设计学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。 实现以下功能: (1)设计校园平面图,在校园景点选10个左右景点。以图中顶点表示校园内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等有关信息。 (2)为来访客人提供图中任意景点相关信息的查询。 (3)为来访客人提供任意景点的问路查询,即查询任意两个景点之间的一条最短路径。 要求:有合理提示;根据提示,可以完成相关的功能要求
时间: 2024-02-27 22:57:06 浏览: 136
好的,下面是一个简单的实现,供你参考:
```
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
using namespace std;
// 定义景点结构体
struct Site {
string name;
string code;
string intro;
};
// 定义边结构体
struct Edge {
int to; // 边的终点
int length; // 路径长度
};
// 定义图类
class Graph {
public:
Graph(int n) {
this->n = n;
adj.resize(n);
sites.resize(n);
dist.resize(n);
visited.resize(n, false);
}
// 添加边
void addEdge(int from, int to, int length) {
Edge e = {to, length};
adj[from].push_back(e);
}
// 添加景点
void addSite(int v, Site site) {
sites[v] = site;
}
// 查询景点信息
void querySite(int v) {
Site site = sites[v];
cout << "景点名称:" << site.name << endl;
cout << "景点代号:" << site.code << endl;
cout << "景点简介:" << site.intro << endl;
}
// 最短路径查询
void shortestPath(int from, int to) {
// 初始化距离数组和标记数组
for (int i = 0; i < n; i++) {
dist[i] = INT_MAX;
visited[i] = false;
}
dist[from] = 0;
// 使用优先队列来加速Dijkstra算法
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, from});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (visited[u]) {
continue;
}
visited[u] = true;
for (auto e : adj[u]) {
int v = e.to;
int w = e.length;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
// 输出最短路径长度和路径
cout << "从 " << sites[from].name << " 到 " << sites[to].name << " 的最短路径长度为:" << dist[to] << endl;
cout << "路径为:";
printPath(from, to);
cout << endl;
}
private:
int n; // 图的顶点数
vector<vector<Edge>> adj; // 邻接表
vector<Site> sites; // 景点数组
vector<int> dist; // 最短距离数组
vector<bool> visited; // 标记数组
// 输出路径
void printPath(int from, int to) {
if (from == to) {
cout << sites[from].name;
} else {
printPath(from, to - 1);
cout << " -> " << sites[to].name;
}
}
};
int main() {
Graph g(10);
// 添加景点
Site site0 = {"教学楼", "JXL", "这是教学楼"};
Site site1 = {"实验楼", "SXL", "这是实验楼"};
Site site2 = {"图书馆", "TSG", "这是图书馆"};
Site site3 = {"体育场", "TYC", "这是体育场"};
Site site4 = {"食堂", "ST", "这是食堂"};
Site site5 = {"宿舍楼A", "SSL-A", "这是宿舍楼A"};
Site site6 = {"宿舍楼B", "SSL-B", "这是宿舍楼B"};
Site site7 = {"游泳馆", "YYG", "这是游泳馆"};
Site site8 = {"篮球场", "LQC", "这是篮球场"};
Site site9 = {"教工宿舍", "JGSS", "这是教工宿舍"};
g.addSite(0, site0);
g.addSite(1, site1);
g.addSite(2, site2);
g.addSite(3, site3);
g.addSite(4, site4);
g.addSite(5, site5);
g.addSite(6, site6);
g.addSite(7, site7);
g.addSite(8, site8);
g.addSite(9, site9);
// 添加边
g.addEdge(0, 1, 100);
g.addEdge(0, 2, 200);
g.addEdge(1, 2, 50);
g.addEdge(1, 3, 150);
g.addEdge(1, 4, 100);
g.addEdge(2, 3, 100);
g.addEdge(2, 4, 150);
g.addEdge(3, 4, 200);
g.addEdge(3, 5, 300);
g.addEdge(3, 6, 350);
g.addEdge(4, 6, 100);
g.addEdge(4, 7, 200);
g.addEdge(5, 6, 150);
g.addEdge(6, 7, 100);
g.addEdge(7, 8, 300);
g.addEdge(8, 9, 400);
// 查询景点信息
g.querySite(2);
// 最短路径查询
g.shortestPath(0, 9);
return 0;
}
```
上面的代码定义了一个Graph类,其中包含了添加边、添加景点、查询景点信息和最短路径查询等函数。在main函数中,我们添加了10个景点和相应的边,然后查询了一个景点的信息,并且计算了从0号景点到9号景点的最短路径。
希望能够帮助你完成相关的功能要求!
阅读全文