篮桥杯的最短路径G 是一个无向图,其中蓝色边的长度是 1 1、橘色边的长度是 2 2、绿色边的长度是 3 3。
时间: 2024-05-14 09:12:48 浏览: 114
无向图最短路径
这道题应该是要求给出从起点到终点的最短路径长度,可以使用 Dijkstra 或者 BFS 算法来解决。
以 Dijkstra 算法为例,首先需要定义一个优先队列(可以使用 STL 中的 priority_queue),每次从队列中取出距离起点最近的点,然后更新与该点相邻的点的最短路径长度。具体实现如下:
```cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
struct Edge {
int v, w;
Edge(int v = 0, int w = 0) : v(v), w(w) {}
};
vector<Edge> G[MAXN];
int dis[MAXN];
bool vis[MAXN];
void dijkstra(int s) {
memset(dis, INF, sizeof(dis));
memset(vis, false, sizeof(vis));
dis[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
pq.push(make_pair(0, s));
while (!pq.empty()) {
int u = pq.top().second; pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].v, w = G[u][i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
pq.push(make_pair(dis[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;
G[u].push_back(Edge(v, w));
G[v].push_back(Edge(u, w));
}
dijkstra(s);
cout << dis[t] << endl;
return 0;
}
```
时间复杂度为 O(mlogn),其中 n 和 m 分别为图的节点数和边数。
阅读全文