# SPFA 算法

{% hint style="success" %}
[洛谷 P3371 【模板】单源最短路径（弱化版）](https://www.luogu.com.cn/problem/P3371)
{% endhint %}

```cpp
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using p = pair<int, int>;
const double pi(acos(-1));
const int inf(0x3f3f3f3f);
const ll _inf(0x3f3f3f3f3f3f3f3f);
const int mod(1e9 + 7);
const int maxn(1e4 + 10);
const int maxm(5e5 + 10);
int ecnt, head[maxn];
ll dis[maxn];
bool vis[maxn];

struct edge {
    int to, wt, nxt;
} edges[maxm];

template<typename T = int>
inline const T read()
{
    T x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

template<typename T>
inline void write(T x, char c)
{
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10, false);
    putchar(x % 10 + '0');
    if (c) putchar(c);
}

void addEdge(int u, int v, int w)
{
    edges[ecnt].to = v;
    edges[ecnt].wt = w;
    edges[ecnt].nxt = head[u];
    head[u] = ecnt++;
}

void spfa(int src)
{
    queue<int> q;
    q.push(src);
    dis[src] = 0;
    vis[src] = true;
    while (not q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; ~i; i = edges[i].nxt) {
            int v = edges[i].to, w = edges[i].wt;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (not vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("input.txt", "r", stdin);
#endif
    memset(head, -1, sizeof head);
    memset(dis, 0x3f, sizeof dis);
    int n = read(), m = read(), s = read();
    while (m--) {
        int u = read(), v = read(), w = read();
        addEdge(u, v, w);
    }
    spfa(s);
    for (int i = 1; i <= n; ++i) {
        write(dis[i] == _inf ? INT_MAX : dis[i], i == n ? '\n' : ' ');
    }
    return 0;
}
```

{% hint style="warning" %}
[洛谷 P4779 【模板】单源最短路径（标准版）](https://www.luogu.com.cn/problem/P4779)
{% endhint %}

![SPFA 已死](/files/-MK95zR6MNRSYe5kGgQN)

```cpp
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using p = pair<int, int>;
const double pi(acos(-1));
const int inf(0x3f3f3f3f);
const ll _inf(0x3f3f3f3f3f3f3f3f);
const int mod(1e9 + 7);
const int maxn(1e5 + 10);
const int maxm(2e5 + 10);
int ecnt, head[maxn];
ll dis[maxn];
bool vis[maxn];

struct edge {
    int to, wt, nxt;
} edges[maxm];

template<typename T = int>
inline const T read()
{
    T x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

template<typename T>
inline void write(T x, char c)
{
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10, false);
    putchar(x % 10 + '0');
    if (c) putchar(c);
}

void addEdge(int u, int v, int w)
{
    edges[ecnt].to = v;
    edges[ecnt].wt = w;
    edges[ecnt].nxt = head[u];
    head[u] = ecnt++;
}

void spfa(int src)
{
    queue<int> q;
    q.push(src);
    dis[src] = 0;
    vis[src] = true;
    while (not q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; ~i; i = edges[i].nxt) {
            int v = edges[i].to, w = edges[i].wt;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (not vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("input.txt", "r", stdin);
#endif
    memset(head, -1, sizeof head);
    memset(dis, 0x3f, sizeof dis);
    int n = read(), m = read(), s = read();
    while (m--) {
        int u = read(), v = read(), w = read();
        addEdge(u, v, w);
    }
    spfa(s);
    for (int i = 1; i <= n; ++i) {
        write(dis[i] == _inf ? INT_MAX : dis[i], i == n ? '\n' : ' ');
    }
    return 0;
}
```

玄学优化 <https://www.luogu.com.cn/blog/xhhkwy/spfa-hacker-orzorz>

![tql](/files/-MLwrL4gCwLLc-FgWS6R)

```cpp
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using p = pair<int, int>;
const double pi(acos(-1));
const int inf(0x3f3f3f3f);
const int mod(1e9 + 7);
const int maxn(1e5 + 10);
const int maxm(1e6 + 10);
int ecnt, head[maxn];
int dis[maxn];
bool vis[maxn];
deque<int> q;

struct edge {
    int to, wt, nxt;
} edges[maxm];

template<typename T = int>
inline const T read()
{
    T x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

template<typename T>
inline void write(T x, char c)
{
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10, false);
    putchar(x % 10 + '0');
    if (c) putchar(c);
}

void addEdge(int u, int v, int w)
{
    edges[ecnt].to = v;
    edges[ecnt].wt = w;
    edges[ecnt].nxt = head[u];
    head[u] = ecnt++;
}

void swap_slf()
{
    if (q.size() > 2 and dis[q.front()] > dis[q.back()]) {
        swap(q.front(), q.back());
    }
}

void spfa(int src)
{
    dis[src] = 0;
    q.push_back(src);
    vis[src] = true;
    while (not q.empty()) {
        int u = q.front();
        q.pop_front();
        swap_slf();
        vis[u] = false;
        for (int i = head[u]; compl i; i = edges[i].nxt) {
            int v = edges[i].to, w = edges[i].wt;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (not vis[v]) {
                    q.push_back(v);
                    swap_slf();
                    vis[v] = true;
                }
            }
        }
    }
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("input.txt", "r", stdin);
#endif
    memset(head, -1, sizeof head);
    memset(dis, 0x3f, sizeof dis);
    int n = read(), m = read(), s = read();
    while (m--) {
        int u = read(), v = read(), w = read();
        addEdge(u, v, w);
    }
    spfa(s);
    for (int i = 1; i <= n; ++i) {
        if (dis[i] == inf) {
            puts("NO PATH");
        } else {
            write(dis[i], i == n ? 10 : 32);
        }
    }
    return 0;
}
```

{% hint style="success" %}
[洛谷 P3385 【模板】负环](https://www.luogu.com.cn/problem/P3385)
{% endhint %}

判断存在负环的条件：1、当前点入列达到 $$n$$ 次；2、源点到当前点的最短（长）路径达到 $$n$$。

两种玄学优化：1、入列计数 `tot >= n * 2` 跳出；2、使用 `stack` 代替 `queue`。

```cpp
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using p = pair<int, int>;
const double pi(acos(-1));
const int inf(0x3f3f3f3f);
const ll _inf(0x3f3f3f3f3f3f3f3f);
const int mod(1e9 + 7);
const int maxn(2e3 + 10);
const int maxm(3e3 + 10);
bool vis[maxn];
int ecnt, head[maxn], cnt[maxn], dis[maxn];

struct edge {
    int to, wt, nxt;
} edges[maxm << 1];

template<typename T = int>
inline const T read()
{
    T x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

template<typename T>
inline void write(T x, char c)
{
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10, false);
    putchar(x % 10 + '0');
    if (c) putchar(c);
}

void addEdge(int u, int v, int w)
{
    edges[ecnt].to = v;
    edges[ecnt].wt = w;
    edges[ecnt].nxt = head[u];
    head[u] = ecnt++;
}

bool spfa(int tot)
{
    queue<int> q;
    vis[1] = true;
    dis[1] = 0;
    q.push(1);
    while (not q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; ~i; i = edges[i].nxt) {
            int v = edges[i].to, w = edges[i].wt;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (not vis[v]) {
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= tot) {
                        return true;
                    }
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return false;
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("input.txt", "r", stdin);
#endif
    int t = read();
    while (t--) {
        ecnt = 0;
        memset(head, -1, sizeof head);
        memset(dis, 0x3f, sizeof dis);
        memset(vis, false, sizeof vis);
        memset(cnt, 0, sizeof cnt);
        int n = read(), m = read();
        while (m--) {
            int u = read(), v = read(), w = read();
            addEdge(u, v, w);
            if (w >= 0) {
                addEdge(v, u, w);
            }
        }
        printf("%s\n", spfa(n) ? "YES" : "NO");
    }
    return 0;
}
```

{% hint style="success" %}
[洛谷 P5960 【模板】差分约束算法](https://www.luogu.com.cn/problem/P5960)
{% endhint %}

差分约束：求最小值→最长路，求最大值→最短路

```cpp
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using p = pair<int, int>;
const double pi(acos(-1));
const int inf(0x3f3f3f3f);
const int mod(1e9 + 7);
const int maxn(5e3 + 10);
const int maxm(1e4 + 10);
bool vis[maxn];
int ecnt, head[maxn], cnt[maxn], dis[maxn];

struct edge {
    int to, wt, nxt;
} edges[maxm];

template<typename T = int>
inline const T read()
{
    T x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

template<typename T>
inline void write(T x, char c)
{
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10, false);
    putchar(x % 10 + '0');
    if (c) putchar(c);
}

void addEdge(int u, int v, int w)
{
    edges[ecnt].to = v;
    edges[ecnt].wt = w;
    edges[ecnt].nxt = head[u];
    head[u] = ecnt++;
}

bool spfa(int n)
{
    memset(dis, 0x3f, sizeof dis);
    dis[0] = 0;
    queue<int> q;
    q.push(0);
    vis[0] = true;
    while (not q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; compl i; i = edges[i].nxt) {
            int v = edges[i].to, w = edges[i].wt;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (not vis[v]) {
                    vis[v] = true;
                    q.push(v);
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n + 1) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    memset(head, -1, sizeof head);
    int n = read(), m = read();
    while (m--) {
        int u = read(), v = read(), w = read();
        addEdge(v, u, w);
    }
    for (int i = 0; i <= n; ++i) {
        addEdge(0, i, 0);
    }
    if (spfa(n)) {
        for (int i = 1; i <= n; ++i) {
            write(dis[i], " \n"[i == n]);
        }
    } else {
        printf("NO\n");
    }
    return 0;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://doc.macrohard.cn/templates/graph/spfa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.