SPFA 模版
给定一个 $n$ 个点，$m$ 条边的有向图，可以使用 $O(nm)$ 的时间复杂度，求出单源点的最短路。
通常复杂度较低，在网格图等特殊情况下将被卡到复杂度的上上界。
使用方法
void SPFA::init(int n); 传入点的数量 n，初始化图
void SPFA::addEdge(int x, int y, int w); 新建一条从 x 到 y 的有向边，边权为 w
void SPFA::solve(int src, int dst); 计算从 src 出发的单源最短路，并返回 src 到 dst 的最短路。
C++代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
namespace SPFA{ const int MAXN = 1e5 + 50; const int INF = 0x3f3f3f3f; queue<int> que; int dist[MAXN], n; bool inQue[MAXN]; vector<pair<int, int> > edge[MAXN]; void init(int n0){ n = n0; for (int i = 0; i <= n; i++){ edge[i].clear(); dist[i] = INF; inQue[i] = false; } } void addEdge(int x, int y, int w){ edge[x].push_back(make_pair(y, w)); } int solve(int src, int dst){ for (int i = 0; i <= n; i++) dist[i] = INF, inQue[i] = false; while(!que.empty()) que.pop(); que.push(src); dist[src] = 0; inQue[src] = true; while(!que.empty()){ int x = que.front(); que.pop(); for (pair<int, int>& e: edge[x]){ int v = e.first, w = e.second; if (dist[v] > dist[x] + w){ dist[v] = dist[x] + w; if (!inQue[v]) que.push(v), inQue[v] = true; } } inQue[x] = false; } return dist[dst]; } }; |
还没有任何评论，你来说两句吧!