职务地址：POJ 1201   HDU 1384

依据题目意思。能够列出不等式例如以下：

Sj-Si>=c;

Si-S(i-1)>=0;

S(i-1)-Si>=-1;

然后用最短路spfa来解决这个不等式。

用max来当源点，0为终点。

终于的-d[0]就是答案。

代码例如以下：

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include <queue>

#include <map>

#include <set>

#include <algorithm>

using namespace std;

const int INF=0x3f3f3f3f;

int d[60000], vis[60000], head[60000], cnt, q[5000000];

struct node

{

    int u, v, w, next;

} edge[1000000];

void add(int u, int v, int w)

{

    edge[cnt].v=v;

    edge[cnt].w=w;

    edge[cnt].next=head[u];

    head[u]=cnt++;

}

void spfa(int s)

{

    memset(d,INF,sizeof(d));

    d[s]=0;

    memset(vis,0,sizeof(vis));

    int ss=0, ee=0;

    q[ss++]=s;

    while(ss>ee)

    {

        int u=q[ee++];

        vis[u]=0;

        for(int i=head[u]; i!=-1; i=edge[i].next)

        {

            int v=edge[i].v;

            if(d[v]>d[u]+edge[i].w)

            {

                d[v]=d[u]+edge[i].w;

                if(!vis[v])

                {

                    vis[v]=1;

                    q[ss++]=v;

                }

            }

        }

    }

}

int main()

{

    int a, b, c, n, i, max1, min1;

    while(scanf("%d",&n)!=EOF)

    {

        memset(head,-1,sizeof(head));

        max1=-1;

        min1=INF;

        cnt=0;

        while(n--)

        {

            scanf("%d%d%d",&a,&b,&c);

            if(max1<b)

                max1=b;

            if(min1>a)

                min1=a;

            add(b,a-1,-c);

        }

        for(i=1; i<=max1; i++)

        {

            add(i-1,i,1);

            add(i,i-1,0);

        }

        spfa(max1);

        printf("%d\n",-d[0]);

    }

    return 0;

}