有一个很明显的贪心结论:一辆飞机要尽可能完成尽可能多的任务。

那个飞机完成$i$任务后,能进行$j$任务的条件为:$D_i+T_{x_i,y_i}+p_{y_i}+f_{y_i,x_j}\le D_j0$,

其中$f_{y_i,x_j}$为$y_i$到$x_j$的最短路径。

因此需要先传递闭包(求最短路)。

把所有合法的$(i,j)$进行连边,题目就被转化成了最小路径覆盖。

用二分图就可以了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<map>
#include<cstdlib>
#include<vector> 
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
using namespace std;
const int N=505,mod=1e9+7;
const ull p0=31,p1=37;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int f[N][N],g[N][N],p[N],D[N],match[N],X[N],Y[N];bool v[N];
struct edge{int y,next;}a[N*N];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
bool dfs(int x)
{
    for(int k=last[x],y;k;k=a[k].next)
    {
        if(!v[y=a[k].y])
        {
            v[y]=1;
            if(!match[y]||dfs(match[y])){match[y]=x;return 1;}
        }
    }
    return 0;
}
int main()
{
    int    n,m;qr(n),qr(m);
    for(int i=1;i<=n;i++)qr(p[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            qr(g[i][j]);
            if(i!=j)f[i][j]=g[i][j]+p[j];
        }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    for(int i=1;i<=m;i++)qr(X[i]),qr(Y[i]),qr(D[i]);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
        {
            if(i==j)continue;
            if(D[i]+g[X[i]][Y[i]]+p[Y[i]]+f[Y[i]][X[j]]<=D[j])ins(i,j);
        }
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        if(dfs(i))++ans;
        memset(v,0,sizeof(v));
    }
    qw(m-ans);puts("");
    return 0;
}