题目描述
You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.Write a program that:
- reads the number of intervals, their end points and integers c1, ..., cn from the standard input,
- computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n,
- writes the answer to the standard output.
输入
The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.输出
The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.样例输入
5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1
样例输出
6
题意：求符合题意的最小集合的元素个数
题目要求的是求的最短路，
则对于 不等式 f(b)-f(a)>=c,建立 一条 b 到 a 的边 权值为 c,则求的最长路 即为 最小值(集合)
并且有隐含条件：0<=f(a)-f(a-1)<=1 则有边权关系(a,a-1,0)以及(a-1,a,-1);
将源点到各点的距离初始化为INF(无穷大)，其中之1为0，最终求出的最短路满足 它们与该点之间相互差值最大