差分约束系统，$spfa$。

首先判断无解，若某个约束的$t$大于区间长度，则一定无解。

否则一定有解，可以得到一系列的不等式：

最终区间和大于等于目前的区间和：$S[R]-S[L-1]≥val$，

每一个位置的值小于等于$1$：$S[R]-S[R-1]≤1$，

每一个约束条件：$S[R]-S[L-1]≥t$，

最终是要求$S[n]-S[0]$最小是多少，扔进差分约束系统，跑$S[0]$到$S[n]$的最长路即可。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;int T;int n,m,k;int dis[2000],f[2000];int h[2200000];int to[2200000];int val[2200000];int nx[2200000];int sz;int a[2000];int cas=1;void add(int a,int b,int c){ to[sz] = b; val[sz] = c; nx[sz] = h[a]; h[a] = sz++;}void spfa(){ for(int i=0;i<=n;i++) dis[i] = -n-1, f[i] = 0; queue
            
             Q; Q.push(0); f[0] = 1; dis[0] =0; while(!Q.empty()) { int x =Q.front(); Q.pop(); f[x]=0; for(int i=h[x];i!=-1;i = nx[i]) { int y = to[i], cost = val[i]; if(dis[x] + cost > dis[y]) { dis[y] = dis[x] + cost; if(f[y]==0) { f[y] = 1; Q.push(y); } } } }}int main(){ scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&k); for(int i=0;i<=n;i++) h[i]=-1, a[i] = 0; sz=0; for(int i=1;i<=k;i++) { int x; scanf("%d",&x); a[x]=1; } for(int i=1;i<=n;i++) { a[i] = a[i]+a[i-1]; add(i,i-1,-1); } bool fail=0; for(int i=1;i<=m;i++) { int L,R,t; scanf("%d%d%d",&L,&R,&t); add(L-1,R,t); if(R-L+1