它是队列优化的Bellman-Ford算法。
优化的原理是：下一次松弛操作时被更新dis的点其实与上一次被更新的点有关！如果上一次被更新的点有一条边指向某点V，那么在下一次，点V就是可能被更新dis的点。
和 Bellman-Ford 算法一样，它可以用来求带负权边的最短路，如果存在一个从源点可以到达的权重为负值的环路，则返回false表示无解决方案，因为可以不断在这个环路中循环使总代价越来越小；如果不存在则返回true。
#include<iostream> #include<algorithm> #include<cstring> #include<string> #include<set> #include<queue> using namespace std; #define INF 0x3f3f3f3f #define M(a, b) memset(a, b, sizeof(a)) const int maxn = 1000 + 5; struct Edge { int from, to, dist; }; struct SPFA { int d[maxn], cnt[maxn], p[maxn]; int n, m; bool inq[maxn]; vector<int> G[maxn]; vector<Edge> edges; void init(int n) { this->n = n; for (int i = 1; i <= n; ++i) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int dist) { edges.push_back(Edge{from, to, dist}); int m = edges.size(); G[from].push_back(m-1); } bool spfa(int s) { M(d, INF); M(cnt, 0); M(inq, 0); d[s] = 0; queue<int> q; q.push(s); inq[s] = true; while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for (int i = 0; i < G[u].size(); ++i) { Edge &e = edges[G[u][i]]; if (d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; p[e.to] = G[u][i]; if (!inq[e.to]) { q.push(e.to); inq[e.to] = true; if (++cnt[e.to] > n) return false; } } } } return true; } }; SPFA solver; int main() { int n, m, a, b, c; while(cin >> m >> n) { solver.init(n); while(m--) { cin >> a >> b >> c; solver.AddEdge(a, b, c); solver.AddEdge(b, a, c); } solver.spfa(1); cout << solver.d[n] << endl; } return 0; }