跟题解中做法有些差别，并没有拆点。

大佬捞捞，玄关

#include<bits/stdc++.h>
using namespace std;
const int MX_N=5010,MX_M=50100,INF=0x3f3f3f3f;
struct node{
    int next,to;
    int w,c;
}edge[MX_M<<1];
int head[MX_N]={0},edge_cnt=0;
inline void Add(int x,int y,int w,int c){
    node &i=edge[edge_cnt];
    i.w=w,i.c=c,i.to=y,i.next=head[x];
    head[x]=edge_cnt++;
}
inline void add(int x,int y,int w,int c){
    // printf("%d %d %d,%d\n",x,y,w,c);
    Add(x,y,w,c),Add(y,x,0,-c);
}
int s=0,t=MX_N-1,S=MX_N-2;
int dist[MX_N]={0},lim[MX_N]={0},pre[MX_N]={0};
bool vis[MX_N]={0};
bool spfa(){
    for(int i=0;i<MX_N;i++)  dist[i]=INF,lim[i]=0,vis[i]=0;
    queue<int>qu;
    qu.push(s);dist[s]=0,lim[s]=INF,vis[s]=1;
    while(!qu.empty()){
        int now=qu.front();qu.pop();vis[now]=0;
        for(int i=head[now];~i;i=edge[i].next){
            int to=edge[i].to,w=edge[i].w,c=edge[i].c;
            if(dist[to]>dist[now]+c&&w){
                dist[to]=dist[now]+c;
                lim[to]=min(lim[now],w);
                pre[to]=i;
                if(!vis[to]){
                    qu.push(to);
                    vis[to]=1;
                }
            }
        }
    }
    return lim[t]>0;
}
void EK(int &flow,int &cost){
    flow=cost=0;
    while(spfa()){
        flow+=lim[t];cost+=lim[t]*dist[t];
        for(int i=t;i!=s;i=edge[pre[i]^1].to){
            edge[pre[i]].w-=lim[t];
            edge[pre[i]^1].w+=lim[t];
        }
    }
}
int d[MX_N]={0};
int mx_end[MX_N]={0},down[MX_N]={0},tim[MX_N]={0};
int ti[MX_N]={0},ai[MX_N]={0},bi[MX_N]={0},sum=0;
signed main(){memset(head,-1,sizeof(head));
    int n,m,k;scanf("%d%d%d",&n,&m,&k);add(s,S,k,0);
    for(int i=2;i<=n;i++)  scanf("%d",&d[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",ti+i,ai+i,bi+i);
        mx_end[ai[i]]=max(mx_end[ai[i]],ti[i]);
        down[bi[i]]++;
    }
    for(int i=2;i<=n;i++)  tim[i]=max(tim[i-1],mx_end[i-1])+d[i];
    for(int i=1;i<=m;i++)  sum+=tim[bi[i]]-ti[i];
    for(int i=2;i<=n;i++){
        add(S,i,d[i],0);
        add(i,t,INF,-down[i]);
        add(i-1,i,max(tim[i-1]-mx_end[i-1],0),-down[i-1]);
    }
    int flow,cost;EK(flow,cost);
    printf("%d",sum+cost);
    return 0;
}