这是网站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]}); // 起点和起点距离起点的距离 放入优先队列
}
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;
}
