Bellman_ford算法

#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)

using namespace std;

int dis[1005]; // dis[i] 表示源点到i的最短路
int g[1005][1005]; // g[i][j] 表示i到j的边权
int n, m, s;

struct Edge
{
    int u, v, w;
} e[10005]; // 边集数组


bool Bellman_ford()
{
    // 1、初始化dis数组
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;

    // 3、重复执行n-1次或者直到不更新为止
    for (int i = 1; i <= n - 1; i++)
    {
        bool flag = true; // 标记是否更新最短路
        // 2、松弛操作
        for (int j = 1; j <= m; j++)
            if (dis[e[j].v] > dis[e[j].u] + e[j].w)
            {
                dis[e[j].v] = dis[e[j].u] + e[j].w;
                flag = false;
            }
        if (flag)
            return true;
    }
    // 4、判断是否存在负环
    for (int j = 1; j <= m; j++)
        if (dis[e[j].v] > dis[e[j].u] + e[j].w)
        {
            dis[e[j].v] = dis[e[j].u] + e[j].w;
            return false; // 存在负环
        }
    return true; // 不存在负环
}

int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    Bellman_ford();
    for (int i = 1; i <= n; i++)
        printf("%d ", dis[i] == 0x3f3f3f3f ? -1 : dis[i]);
    return 0;
}