差分约束（模板）

P5960 【模板】差分约束算法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

• 转换为最短路问题
• i-j<=c转换为i<=j+c表示有一条从j连到i的权值为c的边，设置一个0号源点，与各点都有连线且连线为0.
• 如果以上建成的图存在单源最短路，那么最短路0号源点到各点的距离就是答案
• 如果存在负环那么就不存在最短路，判断负环（松弛次数==n+1就是有负环存在，因为有0号源点所以是n+1）

#include <bits/stdc++.h>
using namespace std;
#define N 1e5
#define INF 2e9
#define MAX 10000000

int head[MAX], idx;
struct Node
{
    int to, dis, nex;
} edge[MAX];
void add(int u, int v, int dis)
{
    edge[++idx] = Node{v, dis, head[u]};
    head[u] = idx;
}
queue<int> q;
int n, m;
int cnt[MAX], dis[MAX];
bool in[MAX];
bool spfa(int start)
{
    q.push(start);
    in[start] = true;
    for (int i = 1; i <= n; i++)
    {
        dis[i] = INF;
    }
    dis[start] = 0;
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        in[now] = false;
        for (int i = head[now]; i; i = edge[i].nex)
        {
            int to = edge[i].to;
            if (dis[to] > edge[i].dis + dis[now])
            {
                dis[to] = edge[i].dis + dis[now];
                if (!in[to])
                {
                    in[to] = true;
                    cnt[to]++;
                    if (cnt[to] == n + 1)
                    {
                        return false;
                    }
                    q.push(to);
                }
            }
        }
    }
    return true;
}
void input()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        add(0, i, 0);
    for (int i = 1, a, b, c; i <= m; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        add(b, a, c);
    }
}
int main()
{
    input();
    if (!spfa(0))
        printf("NO");
    else
        for (int i = 1; i <= n; i++)
            printf("%d ", dis[i]);
}