用c++写一个spfa

很高兴回答您的问题。以下是使用 C 语言编写 SPFA 算法的示例代码：

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

#define MAX_N 100
#define MAX_M 10000

typedef struct {
    int v, w;
} Edge;

Edge edges[MAX_M];
int head[MAX_N], next[MAX_M];
int dist[MAX_N];
bool in_queue[MAX_N];
int queue[MAX_N], front, rear;

int n, m, s;

void add_edge(int u, int v, int w, int i) {
    edges[i].v = v;
    edges[i].w = w;
    next[i] = head[u];
    head[u] = i;
}

void spfa() {
    for (int i = 1; i <= n; i++) {
        dist[i] = INT_MAX;
        in_queue[i] = false;
    }
    dist[s] = ;
    in_queue[s] = true;
    queue[rear++] = s;
    while (front != rear) {
        int u = queue[front++];
        if (front == MAX_N) front = ;
        in_queue[u] = false;
        for (int i = head[u]; i != -1; i = next[i]) {
            int v = edges[i].v, w = edges[i].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!in_queue[v]) {
                    in_queue[v] = true;
                    queue[rear++] = v;
                    if (rear == MAX_N) rear = ;
                }
            }
        }
    }
}

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

希望这个示例代码对您有所帮助。如果您有任何其他问题，请随时问我。