来纪念一下第二次做出 G 题（第一次是 ABC293G，当时作为的学情考察题）。

题意

给你三个长度为 $M$ 的序列 $L=(L_1,L_2,L_3,...,L_M)$，$R=(R_1,R_2,R_3,...,R_M)$，$S=(S_1,S_2,S_3,...,S_M)$，要求构造一个长度为 $N$ 的正整数序列 $A$，使其满足下面的式子：

如果能构造出来，输出找到的所有可能的 $A$ 中总和最小的那个，否则输出 $-1$。

解法

首先注意到这个式子，不妨用前缀和将其代替。令 $s_i=\sum_{j=1}^{i}A_j$，则原式变为

这看着咋感觉有点熟悉？我们将这个式子再变个形：

这不就是差分约束吗！那么我们继续来看，因为我们要构造的是正整数序列，所以一定有 $A_i>0$，即 $A_i\ge1$，所以所一定也有 $s_i-s_{i-1}\ge1$，即 $s_{i-1}-s_i\le-1$，那么这样我们就把图建出来了，然后再跑一遍 SPFA 找负环，找到就输出 $-1$，否则正常输出答案就行了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 15, inf = 1e18;

int n, m;
int head[N], to[N], nxt[N], val[N], idx;//链式前向星
int cnt[N];
bool vis[N];
int dis[N];

void add (int u, int v, int w) {
	to[idx] = v;
	val[idx] = w;
	nxt[idx] = head[u];
	head[u] = idx ++;
}

void spfa () {
    queue<int> q;
    memset (dis, inf, sizeof dis);
    memset (vis, false, sizeof vis);
    memset (cnt, 0, sizeof cnt);
    dis[0] = 0;
    q.push (0);
    vis[0] = true;
    //从 0 号开始：因为前缀和数组默认从 0 号开始累加
    while (!q.empty ()) {
        int u = q.front();
        q.pop ();
        vis[u] = false;
        cnt[u] ++;
        if (cnt[u] > n + 1) {
            puts ("-1");
            return ;
        }
        for (int i = head[u]; i != -1; i = nxt[i]) {
        	int v = to[i], w = val[i];
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    cout << -dis[n] << endl;
    //因为建边的时候是从 i-1 到 i 建了一条权为 -1 的边，这与我们本来的约束方向是相反的，所以输出 -dis[n]
}

signed main () {
	memset (head, -1, sizeof head);
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) {
    	add (i - 1, i, -1);
    }
    for (int i = 1; i <= m; ++ i) {
        int l, r, s;
        cin >> l >> r >> s;
        add (r, l - 1, s);
        add (l - 1, r, -s);
    }
    spfa ();
    return 0;
}

求个赞，不过分吧？

#include <bits/stdc++.h>
using namespace std;
const int N = 4005;
vector<pair<int, int>> G[N];
int n;
long long d[N], dd[N]; bool v[N];// dd[i]记录从出发点到第i个点所经过的点数（不含出发点）
long long spfa()
{
    for (int i = 0; i <= n; ++i)d[i] = -1e18;
    memset(dd, 0, sizeof(dd));
    memset(v, 0, sizeof(v));
    queue<int> q;
    q.push(0);
    d[0] = 0;
    while (!q.empty())
    {
        int x = q.front(); q.pop(); v[x] = 0;
        for (auto i : G[x])
        {
            int y = i.first, w = i.second;
            if (d[y] < d[x] + w)
            {
                d[y] = d[x] + w;
                dd[y] = dd[x] + 1; if (dd[y] > n) return -1ll;
                if (!v[y]) q.push(y), v[y] = 1;
            }
        }
    }
    return d[n];
}
int main()
{
    int m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        int l, r, s;
        scanf("%d%d%d", &l, &r, &s);
        G[l - 1].push_back({ r, s });//  p[l-1]+s <=p[r]      
        G[r].push_back({ l - 1, -s });// p[r]-s <= p[l-1]
    }
    for (int i = 0; i < n; ++i) G[i].push_back({ i + 1, 1 });  // p[i]+1 <= p[i+1] 
    printf("%lld\n", spfa());
    return 0;
}