描述 Description
小杉看了看自己的纹身，明白了整个管道网是由 N 个小房间和若干小房间之间的单向的管道组成的。
小房间编号为不超过 N 的正整数。
对于某个管道，小杉只能在人品不超过一定程度时通过。
小杉一开始在房间 1，现在小杉想知道，每个小房间他最多能够以人品多少的状态到达。
注意，小杉的人品在出发以后是不会改变的。
输入格式 InputFormat
对于一个整数序列，给出的一个三元组 [a，b，c] 表示该序列在闭区间 [a，b] 的整数至少有 c 个，其中 a，b，c 均为整数。
题目将给出 n 个三元组，求同时满足这 n 个三元组的序列的最少元素个数是多少。如果不存在这样的满足要求的序列，则输出－1。
输出格式 OutputFormat
一个数，即为答案
样例输入 SampleInput
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
样例输出 SampleOutput
6
代码 Code
差分约束，最长路。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int inf=0x7fffffff/27.11;
const int maxn=50005;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
int to,next,val;
}e[maxn*5];
int dis[maxn],head[maxn],inq[maxn];
bool used[maxn];
int cnt;
deque <int> q;
inline void ins(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].val=w;e[cnt].next=head[u];
head[u]=cnt;
}
inline bool spfa(int s)
{
int i,j,t,k,u,v,w;
memset(used,false,sizeof(used));
memset(inq,0,sizeof(inq));
for (i=1;i<=n;i++) dis[i]=-inf;
while (!q.empty()) q.pop_front();
q.push_back(s);used[s]=true;dis[s]=0;inq[s]=1;
while (!q.empty())
{
u=q.front();q.pop_front();used[u]=false;
for (i=head[u];i;i=e[i].next)
{
v=e[i].to;w=e[i].val;
if (dis[v]<dis[u]+w)
{
dis[v]=dis[u]+w;
if (!used[v])
{
used[v]=true;
inq[v]++;
if (inq[v]>m) return false;
if (!q.empty() && dis[q.front()]>dis[v]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return true;
}
int main()
{
scanf("%d",&n);
m=0;cnt=0;
for (i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&z);
ins(x-1,y,z);
m=max(m,x);
m=max(m,y);
}
for (i=1;i<=m;i++) ins(i,i-1,-1);
for (i=1;i<=m;i++) ins(i-1,i,0);
if (!spfa(0)) printf("%d\n",-1);
else printf("%d\n",dis[m]);
return 0;
}