圖論訓練 禮物配置設定 [差分限制]

差分限制模闆題，注意判定條件要形成三角限制，不能忘記-1。

禮物配置設定（a.cpp,1s,256MB)

【描述】

為了慶祝大佬wxh的生日，衆人決定為他準備禮物。現在有n個禮品盒排成一行，從1到n編号，每個禮品盒中可能有1個或0個禮品。大佬wxh提出了m個要求，形如“第l[i]到第r[i]個禮品盒當中至少有c[i]個禮品”。現在衆人想知道，為了滿足這些要求，所需準備的最少禮品數。

【輸入】

第一行兩個整數n、m，接下來m行每行三個整數l[i]、r[i]、c[i]。

【輸出】

一行一個整數代表答案。

【樣例輸入】

15 5

3 7 3

8 10 3

6 8 1

1 3 1

10 11 1

【樣例輸出】

6

【限制與約定】

對于30%的資料，n、m<=10。

對于所有資料，n<=1000，m<=10000，1<=l[i],r[i]<=n，0<=c[i]<=r[i]-l[i]+1。

思考

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define maxn 400010
int a[maxn],d[maxn];
bool v[maxn];
int n,m;
int nd[maxn],w[maxn],to[maxn],nxt[maxn],teg=;
void adeg(int p,int q,int r)
{
    to[++teg]=q;
    nxt[teg]=nd[p];
    nd[p]=teg;
    w[teg]=r;
}
queue<int> Q;
bool iq[maxn];
int main()
{
    scanf("%d%d",&n,&m);
    n+=;
    for(int i=; i<n; i++)
    {
        adeg(i,i+,);
        adeg(i+,i,);
    }
    for(int i=; i<=m; i++)
    {
        int p,q,r;
        scanf("%d%d%d",&p,&q,&r);
        adeg(q+,p+,-r);
    }
    for(int i=; i<=n; i++)
    {
        iq[i]=true;
        Q.push(i);
    }
    while(!Q.empty())
    {
        int cur=Q.front(); Q.pop();
        int cd=d[cur]; iq[cur]=false;
        for(int i=nd[cur]; i; i=nxt[i])
            if(cd+w[i]<d[to[i]])
            {
                d[to[i]]=cd+w[i];
                if(!iq[to[i]])
                {
                    iq[to[i]]=true;
                    Q.push(to[i]);
                }
            }
    }
    printf("%d\n",d[n]-d[]);
    return ;
}