加入无向边的权重
时间: 2024-02-12 08:04:51 浏览: 13
如果无向图中的边有权重,可以在输入时同时输入权重,然后在BFS中使用dist数组存储每个节点到起点的最短距离,即每条边的权重之和。
以下是修改后的代码示例:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100005; // 最大节点数
int head[MAXN], nxt[MAXN << 1], ver[MAXN << 1], w[MAXN << 1], tot = 0; // 邻接表存储图和边的权重
int dist[MAXN]; // 存储每个节点到起点的最短距离
bool vis[MAXN]; // 记录每个节点是否已经访问过
void add(int x, int y, int z) { // 添加一条从x到y,权重为z的边
ver[++tot] = y;
w[tot] = z;
nxt[tot] = head[x];
head[x] = tot;
}
void bfs(int s) {
memset(dist, -1, sizeof(dist)); // 初始化dist数组为-1
dist[s] = 0;
vis[s] = true;
int q[MAXN], hh = 0, tt = 0; // 队列
q[0] = s;
while (hh <= tt) {
int u = q[hh++];
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i], d = w[i];
if (!vis[v]) {
dist[v] = dist[u] + d;
vis[v] = true;
q[++tt] = v;
}
}
}
}
int main() {
int n, m; // n是节点数,m是边数
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, z;
cin >> u >> v >> z;
add(u, v, z);
add(v, u, z); // 无向图需要加入反向边
}
int s, t; // 起点和终点
cin >> s >> t;
bfs(s);
cout << dist[t] << endl;
return 0;
}
```
在该示例代码中,每次读入一条边时,同时读入该边的权重z,并将两条相反的边(u到v和v到u)都加入邻接表中。在BFS中,每次遍历到一条从u到v的边时,将v的dist值更新为u的dist值加上该边的权重d,然后将v加入队列中。最后输出dist[t]即可。
示例输入:
```
5 6
1 2 2
1 3 1
2 4 3
2 5 4
3 4 2
4 5 5
1 5
```
表示有5个节点和6条边,其中第1条边连接节点1和2,权重为2,以此类推。最后需要求解从节点1到节点5的最短路径。