python/TangDou/AcWing/ChaFenYueShu/362.cpp

#include <bits/stdc++.h>
using namespace std;
// 这里也可以把[a,b]区间往右移动一个单位，
// 这样就可以空出来S[0]这个点，作为超级原点
const int N = 50010, M = N * 3 + 10;

int dist[N];
int m; // m个区间，可以理解为m条边
bool st[N];
// 邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void spfa() {
    queue<int> q;
    // 求最大路径长度
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    st[0] = true;
    q.push(0);

    while (q.size()) {
        int u = q.front();
        q.pop();
        st[u] = false;
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (dist[v] < dist[u] + w[i]) {
                dist[v] = dist[u] + w[i];
                if (!st[v]) {
                    q.push(v);
                    st[v] = true;
                }
            }
        }
    }
}

int main() {
    cin >> m;
    memset(h, -1, sizeof h);

    /*
    ① s(i)  >= s(i-1) + 0
    ② s(i-1)>= s(i) - 1
    */
    for (int i = 1; i < N; i++) add(i - 1, i, 0), add(i, i - 1, -1);

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        a++, b++;
        add(a - 1, b, c); // s(b) >= s(a-1) + c
    }
    spfa();

    printf("%d\n", dist[50001]);
    return 0;
}