请你按照以下要求编写一个完整的c++代码:二、实验内容 假设以一个带权有向图表示某一区域的公交线路网,图中顶点代表一些区域中的重要场所,弧代表已有的公交线路,弧上的权表示该线路上的票价(或搭乘所需时间),试设计一个交通指南系统,指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。 三、实验步骤 1. 定义结点结构,定义图结构。 2.存储图信息; 3. 定义求任意两点最短路径函数; 4. 写出主函数。
时间: 2024-01-21 15:17:49 浏览: 22
下面是一个基于 Dijkstra 算法的 C++ 实现,可以求解带权有向图的最短路径。
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1005; // 最大顶点数
const int INF = 0x3f3f3f3f; // 无穷大
struct Edge {
int to; // 目标顶点
int weight; // 权值
Edge(int t, int w) : to(t), weight(w) {}
};
vector<Edge> adj[MAXN]; // 邻接表存储图
int dist[MAXN]; // 从起点到每个顶点的最短距离
bool vis[MAXN]; // 标记是否已经访问过
void dijkstra(int s) {
memset(dist, INF, sizeof(dist)); // 初始化距离为无穷大
dist[s] = 0; // 起点到自己的距离为0
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(0, s)); // pair中第一个元素表示距离,第二个元素表示顶点编号
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto e : adj[u]) {
int v = e.to;
int w = e.weight;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push(make_pair(dist[v], v));
}
}
}
}
int main() {
int n, m, s, t;
cin >> n >> m >> s >> t;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back(Edge(v, w)); // 添加一条有向边
}
dijkstra(s); // 求解最短路径
if (dist[t] == INF) {
cout << "No path from " << s << " to " << t << endl;
} else {
cout << "Shortest path from " << s << " to " << t << " is " << dist[t] << endl;
}
return 0;
}
```
代码中使用了一个邻接表来存储图结构,并使用了 Dijkstra 算法来求解任意两点之间的最短路径。在主函数中,我们首先读入图的信息,并调用 dijkstra 函数来求解最短路径。最后输出结果即可。
注意:本代码仅供参考,实际应用中需要根据具体情况进行修改。