poj 1201 Intervals 差分约束+spfa

     利用相互关系进行约束，求最长路

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
struct edge
{
    int len,nn;
};
int ss,ee,dis[50005];
queue<int> q;
bool in[50005];
vector<edge> map[50005];
int spfa()
{
    int i,now,k,next,t;
    while(!q.empty())q.pop();
    memset(in,0,sizeof(in));
    for(i=ss; i<=ee; i++) dis[i]=-INF;
    in[ss]=1;
    dis[ss]=0;
    q.push(ss);
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        in[now]=0;
        k=map[now].size();
        for(i=0; i<k; i++)
        {
            next=map[now][i].nn;
            if(dis[next]>=(t=dis[now]+map[now][i].len))continue;
            dis[next]=t;
            if(in[next])continue;
            q.push(next);
            in[next]=1;
        }
    }
    return dis[ee];
}
int main()
{
    int i,n,a,b,c;
    edge temp;
    while(~scanf("%d",&n))
    {
        for(i=0; i<50005; i++)map[i].clear();
        ss=INF;
        ee=-1;
        while(n--)
        {
            scanf("%d%d%d",&a,&b,&c);
            b++;
            if(a<ss)ss=a;
            if(b>ee)ee=b;
            temp.len=c;
            temp.nn=b;
            map[a].push_back(temp);
        }
        for(i=ss; i<=ee; i++)
        {
            temp.len=0;
            temp.nn=i+1;
            map[i].push_back(temp);
            temp.len=-1;
            temp.nn=i;
            map[i+1].push_back(temp);
        }
        printf("%d\n",spfa());
    }
    return 0;
}