最短路算法 dijkstra 从认识到熟练掌握
参考资料:(这里鸣谢代码随想录的分享)
Dijkstra算法，你的最短路来了！(认识dijkstra)
Dijkstra算法，求最短路还能更快！(堆优化版)
个人总结的代码
下面的代码可以AC P4779 【模板】单源最短路径（标准版） - 洛谷
相信你通过上面的参考资料或者下面的代码总结属于你自己的dijkstra
#include using namespace std;class Dist{public: int u; int d; Dist(int u_, int d_):u(u_),d(d_){} bool operator < (const Dist &other) const{ return d > other.d;// 小顶堆 }};void solve() { int n, m, start; // n为顶点 m为边数 cin >> n >> m >> start; priority_queue q; vector g; for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; g.push_back(Dist(v, w)); } vector vis(n + 1, false); vector dis(n + 1, INT_MAX); q.push(Dist(start, 0)); dis = 0; while (!q.empty()) { Dist cur = q.top(); q.pop(); int u = cur.u; if(vis) continue; vis = true; for(auto &next:g){ int v = next.u; if(dis > dis + next.d){ dis = dis + next.d; q.push(Dist(v, dis)); } } } for(int i = 1;i
页:
[1]