差分约束模版

思路

将不等式转化为有向图路径长度：di-dj<=k;利用spfa以0为源点求最短路径，d(i)为xi的最大值;
想求最小值，边权加负号，即可。

题目

牛客round 58 G随机化游戏时间

模版

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include <sstream>
#include<map>
using namespace std;
#define int long long
//#define ll long long
typedef pair<int, int> PII;
const int N = 4e5 + 10;
vector<PII> edge[N];
void addedge(int x, int y, int z) {
    edge[x].push_back({ y,z });
}
int dis[N], vis[N];
int n, m;
void spfa(int s) {
    for (int i = 0; i <= n; i++) {
        dis[i] = 1e9;
        vis[i] = 0;
    }
    queue<int> q;
    dis[s] = 0;
    vis[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (auto t : edge[u]) {
            int v = t.first;
            int w = t.second;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}
signed main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 0; i <= n; i++)
            while(!edge[i].empty())edge[i].pop_back();
        while (m--) {
            int l, r, k;
            cin >> l >> r >> k;
            addedge(l - 1, r, k);
            addedge(r, l - 1, -k);
        }
        for (int i = 0; i < n; i++) {
            addedge(i, i + 1, 1);
            addedge(i + 1, i, 0);
        }
        spfa(0);
        int r = dis[n];
        spfa(n);
        int l = dis[0];
        l = -l;
        for (int i = max(1LL, l); i <= min(r, n); i++) {
            cout << i << " ";
        }
        cout << "\n";
    }
}