最短路第 7 题

2023-07-29 14:26:52

发布于：河北

6阅读

0回复

0点赞

这是网站https://www.yuque.com/u1548733/xqntvc/zee2xczpf4nu0b0a

这是代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25e2 + 5;
struct Edge {
// 边的终点 v，边的权值 w
int v, w;
// 优先队列排序规则 w 越小排在前面
bool operator< (const Edge &a) const {
return a.w < w;
}
};
// 图
vector<Edge> g[MAXN];
// dist 表示从源点到各个点的距离
int dist[MAXN], n, m, a, b;
priority_queue<Edge> q; // 每次提取距离起点最近的点
const int INF = 1e9; // 表示非常远

void D() {
// 1. 把所有的点标记未访问不到(无穷远)
for (int i = 1; i <= n; i++) {
dist[i] = INF; // 标记非常大的数字表示距离起点无穷远
}
dist[a] = 0; // 起点相当于站在原地，距离 0
q.push((Edge){a, dist[a]}); // 起点和起点距离起点的距离放入优先队列

while (!q.empty()) {					// 当队列中还有顶点可以走最短路 
	int u = q.top().v, w = q.top().w;	// 取出距离起点最近的点，并且这个时候距离起点的距离 w 
	q.pop();							// 删除队首 
	if (dist[u] < w) continue;			// 如果表上记录的最短值 < 现在记录起点到 u 的距离w 
	
	for (auto e : g[u]) {				// 遍历所有可以到达的点 
		int v = e.v, road = dist[u] + e.w;	// u->v 某一条边 w，a->u->v：dist[u] + e.w
		if (dist[v] > road) {			// 从 a->v 若 > 现在 a->u->v，更新最小值
			dist[v] = road;
			q.push((Edge){v, dist[v]});	// a->v 终点最短距离被更新，那么放入优先队列，供下一次提取
		}
	}
}

}

int main() {
cin >> n >> m >> a >> b; // n 顶点，m 条边，a 起点，b 终点
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back((Edge){v, w}); // u->v 权重 w
g[v].push_back((Edge){u, w}); // v->u 权重 w
}
D(); // dijkstra 最短路
cout << dist[b]; // a 点到 b 点最短距离
return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 2

广州地铁
《43分钟前，来自北京》

2026-02-05 来自广东
0
烛夜
顶

2026-02-05 来自北京
0

全部评论 2

热门讨论