hdu 1384 差分约束(SPFA实现)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 100010
int head[MAXN],n,m,Min,Max,dist[MAXN];
struct Edge{
    int to,next,w;
}e[MAXN*3];
void add_edge(int u,int v,int c){
    e[m].to=v;
    e[m].w=c;
    e[m].next=head[u];
    head[u]=m++;
}
void SPFA(int s){
    bool vis[MAXN];
    memset(vis,false,sizeof(vis));
    for(int i=Min;i<=Max+1;i++)dist[i]=-10000;
    queue<int> que;
    que.push(s);
    vis[s]=false;
    dist[s]=0;
    while(!que.empty()){
        int u=que.front();
        que.pop();
        vis[u]=false;
        int k=head[u];
        while(k>=0){
            if(dist[e[k].to]<dist[u]+e[k].w){
                dist[e[k].to]=dist[u]+e[k].w;
                if(!vis[e[k].to]){
                    que.push(e[k].to);
                    vis[e[k].to]=true;
                }
            }
            k=e[k].next;
        }
    }
}
void init(){
    memset(head,-1,sizeof(head));
    int a,b,c;
    Max=m=0;
    Min=MAXN;
    for(int i=0;i<n;i++){
        scanf("%d%d%d",&a,&b,&c);
        Min=min(Min,a);
        Max=max(Max,b);
        add_edge(a,b+1,c);
    }
    for(int i=Min;i<=Max;i++){
        add_edge(i,i+1,0);
        add_edge(i+1,i,-1);
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        init();
        SPFA(Min);
        printf("%d\n",dist[Max+1]);
    }
    return 0;
}