题目描述作物杂交是作物栽培中重要的一步。已知有 �N 种作物 编号 11 至 �N 第 �i 种作物从播种到成熟的时间为 ��T i 。作物之间两两可以进行杂交杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天作物 B 种植时间为 7 天则 AB 杂交花费的时间为 7 天。作物杂交会产生固定的作物新产生的作物仍然属于 �N 种作物中的一种。初始时拥有其中 �M 种作物的种子 数量无限

题意

有 $n$ 个作物，第 $i$ 个作物从播种到成熟的时间为 $t_i$，两种作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方，杂交会产生固定的作物，新产生的作物仍然属于 $n$ 种作物中的一种。有 $m$ 种作物的种子，求得到给定的目标种子 $D$ 最少需要多少天。

输入格式

第一行包含 $n,m,k,t,N$，分别表示作物种类总数，初始拥有的作物种子类型数量，可以杂交的方案数，目标种子的编号，总共运行天数。

第二行包含 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 种作物的种植时间 $t_i$。

第三行包含 $m$ 个整数，分别表示已拥有的种子类型。

接下来 $k$ 行，每行包含三个整数 $A,B,C$，表示第 $A$ 类作物和第 $B$ 类作物杂交可以获得第 $C$ 类作物的种子。

输出格式

输出一个整数，表示得到目标种子的最短杂交时间。

数据范围

$1≤n≤2000,2≤m≤n,1≤k≤10^5,1≤t≤n$

输入样例

6 2 4 6 5 3 4 6 4 9 1 2 1 2 3 1 3 4 2 3 5 4 5 6

输出样例

算法1

(搜索) $O(n^3)$

从初始状态开始，搜索当前状态的可行的下一步状态，直到找到目标状态。 此处搜索的状态是一个集合，表示我们已经拥有了哪些作物的种子。

时间复杂度

搜索的状态大概率不会太多，因此时间复杂度和搜索状态的数量有关，一般情况下为搜索树的叶子节点数量，是比较小的。

C++ 代码

算法2

(拓扑排序) $O(n^2)$

我们考虑对当前的状态建图，从而进行拓扑排序，得到最短的时间。 对于每一个状态，我们可以找到它所有可行的下一步状态，把它们连接起来，这样就得到了一个有向无环图。 然后我们对这张图进行拓扑排序，从初始状态开始，每次从队列中取出一个状态，考虑所有它指向的状态，如果这些状态的前驱节点都已经确定了，就可以把这些状态加入队列。这样不断进行下去，直到到达目标状态为止。

时间复杂度

每个状态最多会被加入队列一次，而每次加入队列时需要 $O(n)$ 的时间计算后继状态，因此总时间复杂度是 $O(n^2)$。

C++ 代码

算法3

(二分答案) $O((n^2+m)\log T)$

如果 $T$ 很大，我们可以考虑进行二分答案。二分答案的目标是找到一个时间 $t$，使得在 $t$ 天内可以得到目标作物的种子，但是 $t-1$ 天的时候无法得到目标作物的种子。 我们考虑对于每个时间 $t$，计算在 $t$ 天内是否能得到目标作物的种子。这个问题可以通过拓扑排序解决，时间复杂度为 $O((n^2+m)\log T)$。

时间复杂度

算法的时间复杂度是 $O((n^2+m)\log T)$。

C++ 代码