知识点：

1、拓扑排序

解题思路：

• 使用拓扑排序，寻找入度为零的点
• 输出当前的这个入度为0的点
• 将这个点所连接的所有点的入度减一
• 找到一个点，将其入队

2、dp

• 由于要求最小时间，初始状态$f_i$设为$t_i$
• 在遍历时寻找每个点的时间，及将当前节点$f_v$转移过来的时间与他的上一个节点$f_u$所需的时间加上当前节点单独需要的时间$t_v$进行比较，取最大值

思路：

1. 初始化

• 输入每个节点的时间时，将时间设为动态转移方程的初始值

拓扑排序

• 先将入度为0的节点入队，遍历这个点所指向的节点
• 由于减少了一个节点，它所指向的节点的入度会减$1$
• 进行转移
• 如果当前被遍历到的节点的入度为$0$
• 最后对$dp$数组进行遍历，寻求最终答案

代码：

# include <bits/stdc++.h>
# define int long long
# define endl '\n'
# define str string
# define fst ios::sync_with_stdio (0); cin.tie (0); cout.tie (0);

using namespace std;

const int N = 1e6 + 5, M = 2e6 + 5;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int LNF = 0x3f3f3f3f3f3f3f3f;

int n, m;
int in[N];
int t[N];
vector < int > mp[N];
queue < int > q;
int f[N];
int ans;

inline void bfs () {
	while (! q.empty ()) { 
		int u = q.front (); // 删除入度为0的节点 
		q.pop ();
		for (int v : mp[u]) { // 对图进行遍历 
			in[v] --; // 由于少了一个节点，所以它所指向的节点的入度数量需要减1 
			f[v] = max (f[v], (t[v] + f[u])); // 动态转移方程 
			if (! in[v]) { // 如果又有节点入度为0说明需要进行新的拓扑排序 
				q.push (v);
			}
		}
	}
}

inline void top_sort () { // 进行拓扑排序 
	for (int i = 1; i <= n; i ++ ) { // 将入度为0的节点进行入队 
		if (! in[i]) {
			q.push (i);
		}
	}
	bfs ();
	for (int i = 0; i < N; i ++ ) { // 求解最终答案 
		ans = max (ans, f[i]);
	}
	cout << ans;
}

signed main () {
//	fst;
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; i ++ ) { 
		cin >> t[i];
		f[i] = t[i]; // 初始化dp数组 
	}
	for (int i = 1, u, v; i <= m; i ++ ) {
		cin >> u >> v;
		mp[u].push_back (v); // 建图 
		in[v] ++; // 存下入度 
	}
	top_sort ();
	return 0;
}
···