SPFA（Shortest path faster algorithm）
算法思想基于Bellman-Ford算法
进行优化的方式是 在进行某一次松弛操作中 如果起点到一个点的距离不变 那么以这个点为中转点能到达的点距起点的距离不变
如果这个点的距离发生了变化 就将这个点入队列 以求通过这个点中转的点距起点的位置是否发生了变化
vis数组标记当前位于队列中的顶点
显然 一个顶点出队列时 要取消标记
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false) #define endl '\n' using namespace std; typedef long long ll; typedef pair<int, int>p; const int maxn = 205; int n, m; int d[maxn], vis[maxn]; vector<p>vec[maxn]; void init() { for (int i = 0;i < maxn;++i)d[i] = INF; for (int i = 0;i < maxn;++i)vec[i].clear(); for (int i = 0;i < maxn;++i)vis[i] = 0; } int main() { while (~scanf("%d %d", &n, &m)) { init(); for (int i = 0;i < m;++i) { //无向图 int x, y, z;cin >> x >> y >> z; vec[x].push_back(make_pair(y, z)); vec[y].push_back(make_pair(x, z)); } int s, t;cin >> s >> t; queue<int>q; d[s] = 0; q.push(s); vis[s] = 1; while (!q.empty()) { int now = q.front(); q.pop();vis[now] = 0; for (int i = 0;i < vec[now].size();++i) { int v = vec[now][i].first; if (d[v] > d[now] + vec[now][i].second) { d[v] = d[now] + vec[now][i].second; if (!vis[v]) { vis[v] = 1; q.push(v); } } } } if (d[t] == INF)printf("-1\n"); else printf("%d\n", d[t]); } }
