zoj 1508 Intervals

#include <cstdio>#include <cstring>#include <iostream>#include <stack>using namespace std;const int INF=0x3fffffff;const int N=50006;const int E=160006;struct Edge{    int st, en, val, next;    Edge() {}    Edge(int a, int b, int c, int d)    {        st=a, en=b, val=c, next=d;    }} edge[E];int head[N], tot;int cnt[N], dis[N];bool vs[N];stack<int> S;void add_edge(int st, int en, int val){    edge[tot]=Edge(st, en, val, head[st]);    head[st]=tot++;}int SPFA(int s, int t, int n){    for(int i=0; i<=n; i++) vs[i]=false, dis[i]=-INF, cnt[i]=0;    while(!S.empty()) S.pop();    S.push(s), vs[s]=true, dis[s]=0, cnt[s]++;    while(!S.empty())    {        int u=S.top();        S.pop(), vs[u]=false;        if(cnt[u]>n) return -1;        for(int e=head[u]; e!=-1; e=edge[e].next)        { int v=edge[e].en; int val=edge[e].val; if(dis[v]<dis[u]+val) {     dis[v]=dis[u]+val;     if(!vs[v]) vs[v]=true, S.push(v), cnt[v]++; }        }    }    return dis[t];}int main(){    int n;    while(scanf("%d", &n)!=EOF)    {        memset(head, -1, sizeof head);        tot=0;        int Max=0;        for(int i=0, a, b, c; i<n; i++)        { scanf("%d%d%d", &a, &b, &c); Max=max(Max, b); add_edge(a, b+1, c);        }        for(int i=1; i<=Max+1; i++) add_edge(i, i-1, -1), add_edge(i-1, i, 0);        int ans=SPFA(1, Max+1, Max+1);        printf("%dn", ans);    }    return 0;}