poj1201差分约束

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
#include<stack>
#include<list>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include <fstream>
using namespace std;
const int maxn=50005;

int n;
int head[maxn];
int len;
int dis[maxn];
int vis[maxn];
struct Node
{
    int to;int val;int next;
}e[11111111];

void add(int from,int to,int val)
{
    e[len].to=to;
    e[len].val=val;
    e[len].next=head[from];
    head[from]=len++;
}
const int INF=0xfffffff;
int Max;
int cnt[maxn];
int spfa(int x)
{
    for(int i=0;i<=Max;i++)
        dis[i]=INF;
    memset(vis,0,sizeof(vis));
    dis[x]=0;vis[x]=1;
    queue<int> q; q.push(x);
    while(!q.empty()){
        int cur=q.front();q.pop();vis[cur]=0;
        for(int i=head[cur];i!=-1;i=e[i].next){
            int cc=e[i].to;
            if(dis[cc]>dis[cur]+e[i].val){
                dis[cc]=dis[cur]+e[i].val;
                if(!vis[cc]){
                    vis[cc]=1;cnt[cc]++;if(cnt[cc]>n) return 0;
                    q.push(cc);
                }
            }
        }
    }
    return 1;
}
int main()
{
    while(cin>>n){
        Max=0;
        int len=0;memset(head,-1,sizeof(head));
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;i++){
            int a;int b;int c;cin>>a>>b>>c;
            if(b>Max) Max=b;a--;add(b,a,-c);
        }
        for(int i=0;i<=Max-1;i++)
            add(i,i+1,1);
        for(int i=1;i<=Max;i++)
            add(i,i-1,0);
        int t=spfa(Max);
        if(t) cout<<-dis[0]<<endl;
    }
    return 0;
}