zoj 2770 Burn the Linked Camp 差分约束

  最近状态太散漫，一天才写了这一题，很基础的差分约束，直接写出关系式即可。注意边数开大点

/*
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;
int Dis[1005];
int U[100005];
int next[100005];
int W[100005];
int cnt;
int first[1005];
int n,m;
int add(int v,int u,int w)
{
    next[cnt]=first[v];
    first[v]=cnt;
    U[cnt]=u;
    W[cnt]=w;
    cnt++;
}
bool inq[1005];
int dq[1005];
bool spfa(int v)
{
    memset(Dis,63,sizeof(Dis));
    memset(inq,0,sizeof(inq));
    memset(dq,0,sizeof(dq));
    queue<int> q;
    q.push(v);
    Dis[v]=0;
    int i,u,now,t;
    while(!q.empty())
    {
        v=q.front();q.pop();
        inq[v]=0;dq[v]++;
        if(dq[v]>=n)return 1;
        for(i=first[v];i!=-1;i=next[i])
        {
            u=U[i];
            t=Dis[v]+W[i];
            if(t>=Dis[u])continue;
            Dis[u]=t;
            if(inq[u])continue;
            inq[u]=1;
            q.push(u);
        }
    }
    return 0;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;
        memset(first,-1,sizeof(first));
        int i,v,u,s;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&s);
            add(i-1,i,s);
            add(i,i-1,0);
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&s);
            add(v,u-1,-s);
        }
        if(spfa(n))printf("Bad Estimations\n");
        else printf("%d\n",-Dis[0]);
    }
}