作物杂交 ### 题目描述 作物杂交是作物栽培中重要的一步。已知有 $N$ 种作物 (编号 $1$ 至 $N$ )，第 $i$ 种作物从播种到成熟的时间为 $T_i$。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天，作物 B 种植时间为 7 天，则 AB 杂交花费的时间为 7 天。作物杂交会产生固定的作物，新产生的作物仍然属于 $N$ 种作物中的一种。 初始时，拥有其中 $M$ 种作物的种子 (数量无限，可以支持多次杂交)。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。 如存在 4 种作物 ABCD，各自的成熟时间为 5 天、7 天、3 天、8 天。初始拥有 AB 两种作物的种子，目标种子为 D，已知杂交情况为 A × B → C，A × C → D。则最短的杂交过程为： 第 1 天到第 7 天 (作物 B 的时间)，A × B → C。 第 8 天到第 12 天 (作物 A 的时间)，A × C → D。 花费 12 天得到作物 D 的种子。 ### 输入描述 输入的第 1 行包含 4 个整数 $N, M, K, T$，$N$ 表示作物种类总数 (编号 $1$ 至 $N$)，$M$ 表示初始拥有的作物种子类型数量，$K$ 表示可以杂交的方案数，$T$ 表示目标种子的编号。 第 2 行包含 $N$ 个整数，其中第 $i$ 个整数表示第 $i$ 种作物的种植时间 $T_i\ (1 \leq T_i \leq 100)$。 第 3 行包含 $M$ 个整数，分别表示已拥有的种子类型 $K_j\ (1 \leq K_j \leq M)$，$K_j$ 两两不同。 第 4 至 $K$ + 3 行，每行包含 3 个整数 $A, B,C$，表示第 $A$ 类作物和第 $B$ 类作物杂交可以获得第 $C$ 类作物的种子。 其中，$1 \leq N \leq 2000, 2 \leq M \leq N, 1 \leq K \leq 10^5, 1 \leq T \leq N$, 保证目标种子一定可以通过杂交得到。 ### 输出描述 输出一个整数，表示得到目标种子的最短杂交时间。 ### 输入输出样例 #### 示例 >输入 ```txt 6 2 4 6 5 3 4 6 4 9 1 2 1 2 3 1 3 4 2 3 5 4 5 6 ``` >输出 ```txt 16 ``` >样例说明 第 1 天至第 5 天，将编号 1 与编号 2 的作物杂交，得到编号 3 的作物种子。 第 6 天至第 10 天，将编号 1 与编号 3 的作物杂交，得到编号 4 的作物种子。 第 6 天至第 9 天，将编号 2 与编号 3 的作物杂交，得到编号 5 的作物种子。 第 11 天至第 16 天，将编号 4 与编号 5 的作物杂交，得到编号 6 的作物种子。 总共花费 16 天。