SPFA的C语言实现，用顺序队列实现

好的，以下是SPFA算法的C语言实现，使用顺序队列实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAXN 1005
#define MAXM 200005
#define INF 0x3f3f3f3f

int head[MAXN], cnt = 0;
int dis[MAXN], cntq[MAXN];
bool vis[MAXN];
int q[MAXM], front = 0, rear = -1;

struct edge {
    int to, next, w;
} e[MAXM];

void add(int u, int v, int w) {
    e[++cnt].to = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}

void spfa(int s, int n) {
    front = 0, rear = -1;
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    memset(cntq, 0, sizeof(cntq));
    dis[s] = 0;
    vis[s] = true;
    q[++rear] = s;
    cntq[s]++;

    while (front <= rear) {
        int u = q[front++];
        vis[u] = false;

        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].to;
            if (dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if (!vis[v]) {
                    vis[v] = true;
                    q[++rear] = v;
                    cntq[v]++;
                    if (cntq[v] > n) {
                        printf("存在负环\n");
                        return;
                    }
                }
            }
        }
    }
}

int main() {
    int n, m, s;
    memset(head, -1, sizeof(head));
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    spfa(s, n);
    for (int i = 1; i <= n; ++i) {
        printf("%d ", dis[i]);
    }
    printf("\n");
    return 0;
}

其中，`head[]`用于存储每个点的第一条边的编号，`dis[]`用于存储当前点到起点的最短距离，`vis[]`用于标记当前点是否在队列中，`cntq[]`用于记录每个点进入队列的次数，`q[]`为顺序队列。在SPFA算法中，首先将起点加入队列中，并将其距离设为0。然后从队列中取出一个点，遍历其所有出边，若找到了一条可以更新距离的边，则将该边指向的点加入队列中。若该点已经在队列中，则不需要重复加入。当某个点进入队列的次数超过节点数时，说明存在负环，算法结束。最后，输出每个点到起点的最短距离即可。