最短路第 7 题
2023-07-29 14:26:52
发布于：河北
这是网站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;
}
这里空空如也
有帮助，赞一个