题目链接：https://www.luogu.com.cn/problem/P1250
题目大意：略
解题思路：差分约束 求 最长路。
关于为什么求最长路可以看一下这边博客：《关于差分约束系统中跑最长路还是最短路的澄清》
博客的核心思想就是一句话：
要想求最小解集跑最长路；要想求最大解集跑最短路。
这也加深了我对差分约束问题的理解。
示例程序：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e4 + 5;
struct Edge { int v, w; };
vector<Edge> g[maxn];
int T, n, m;
int dis[maxn];
bool inq[maxn];
void spfa() {
queue<int> que;
memset(dis, -1, sizeof(int)*(n+1));
dis[0] = 0;
que.push(0);
while (!que.empty()) {
int u = que.front();
que.pop();
inq[u] = false;
for (auto e : g[u]) {
int v = e.v, w = e.w;
if (dis[v] < dis[u] + w) {
dis[v] = dis[u] + w;
if (!inq[v])
inq[v] = true, que.push(v);
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int b, e, t;
scanf("%d%d%d", &b, &e, &t);
g[b-1].push_back({e, t});
}
for (int i = 1; i <= n; i++)
g[i-1].push_back({i, 0}),
g[i].push_back({i-1, -1});
spfa();
printf("%d\n", dis[n]);
return 0;
}