Description：

有若干航线，每条航线从 $A$ 到 $B$ 在 $D$ 时刻出发，给出从每个点到另一个点的最短路，在机场中转需要加油，问最少需要多少飞机。

$1\leqslant n\leqslant500$

Solution：

先用 $floyed$ 预处理出两两点最短路，然后把航线看成点，如果可以有一架飞机在飞完 $a$ 后还来得及飞 $b$ ，那么就在他们之间连一条边，这样连出来一定是一个 $\text{DAG}$ ，问题就变成了最小路径覆盖，拆点二分图求最大匹配即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 510

int maintain_time[MAXN];

int dis[MAXN][MAXN],dist[MAXN][MAXN];

int x[MAXN],y[MAXN],d[MAXN];

int s,t;

struct edge

{

	int to,nxt,f;

}e[MAXN * 2 * 2 + MAXN * MAXN * 2];

int edgenum = 0;

int lin[MAXN << 1];

void add(int a,int b,int f)

{

	e[edgenum].to = b;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

int ch[MAXN << 1];

bool BFS()

{

	memset(ch,-1,sizeof(ch));ch[s] = 0;

	queue<int> q;q.push(s);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return (ch[t] != -1);

}

int flow(int k,int f)

{

	if(k == t)return f;

	int r = 0;

	for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			int l = flow(e[i].to,min(e[i].f,f - r));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

#define INF 0x3f3f3f3f

int dinic()

{

	int ans = 0,r;

	while(BFS())while(r = flow(s,INF))ans += r;

	return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&maintain_time[i]);

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= n;++j)

		{

			scanf("%d",&dis[i][j]);dist[i][j] = dis[i][j];

			if(i != j)dis[i][j] += maintain_time[j];

		}

	}

	for(int k = 1;k <= n;++k)

		for(int i = 1;i <= n;++i)

			for(int j = 1;j <= n;++j)

				dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);

	s = 0,t = 1;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&x[i],&y[i],&d[i]);

		add(s,i * 2 + 1,1);add(i * 2 + 2,t,1);

	}

	for(int i = 1;i <= m;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			if(i == j)continue;

			if(d[i] + dist[x[i]][y[i]] + maintain_time[y[i]] + dis[y[i]][x[j]] <= d[j])

			{

				add(i * 2 + 1,j * 2 + 2,1);

			}

		}

	}

	cout << m - dinic() << endl;

	return 0;

}