题目链接：

用户登录https://www.lanqiao.cn/problems/506/learning/?page=2&first_category_id=1&sort=students_count

题目描述

作物杂交是作物栽培中重要的一步。已知有 N 种作物 (编号 1 至 N )，第 i 种作物从播种到成熟的时间为 Ti​。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物 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 种作物的种植时间 Ti。

第 3 行包含 M 个整数，分别表示已拥有的种子类型 Kj 两两不同。

第 4 至 K + 3 行，每行包含 3 个整数 A, B,C表示第 A类作物和第 B类作物杂交可以获得第 C 类作物的种子。

输出描述

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

输入输出样例

示例

输入

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

输出

16

样例说明

第 1 天至第 5 天，将编号 1 与编号 2 的作物杂交，得到编号 3 的作物种子。

第 6 天至第 10 天，将编号 1 与编号 3 的作物杂交，得到编号 4 的作物种子。

第 6 天至第 9 天，将编号 2 与编号 3 的作物杂交，得到编号 5 的作物种子。

第 11 天至第 16 天，将编号 4 与编号 5 的作物杂交，得到编号 6 的作物种子。

总共花费 16 天。

题目代码：

import java.util.Scanner;
/*
3 2 1 3
5 3 4
1 2
1 2 3*/
public class 作物杂交 {static zajiao[] p;static int[] a, b, f;static int n, m, k, t;static int[] Min;static int[] Maxtime;public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);n = sc.nextInt();// 编号m = sc.nextInt();// 初始种子数量k = sc.nextInt();// 杂交方案t = sc.nextInt();// 目标种子编号a = new int[n + 1];// 每个编号对应种子成熟时间for (int i = 1; i <= n; i++) {a[i] = sc.nextInt();}f = new int[n + 1]; // 标记已有的种子编号b = new int[n + 1];// 已有的种子编号Min = new int[n + 1];// 记录交配最小时间Maxtime = new int[k];// 杂交交配取两个最长的那一个for (int i = 1; i <= m; i++) {b[i] = sc.nextInt();f[b[i]] = 1;}p = new zajiao[k];// 存放初始交配方案for (int i = 0; i < k; i++) {int c1 = sc.nextInt();int c2 = sc.nextInt();int c3 = sc.nextInt();p[i] = new zajiao(c1, c2, c3);Maxtime[i] = Math.max(a[c1], a[c2]);// 取最大时间}System.out.println(time(t));// 目标种子}public static int time(int t) {if (f[t] == 0) {// 已有的种子没有标记就要去寻找最短时间int min = Integer.MAX_VALUE;for (int i = 0; i < k; i++) {if (p[i].c == t) {// 寻找目标种子,向前递归// 计算最短时间,当前最大时间+上一次的最大时间min = Math.min(min, Maxtime[i] + Math.max(time(p[i].b), time(p[i].a)));}}f[t] = 1;// 找到了就标记加入Min[t] = min;//存储到对应的最小时间位置return min;  //返回当前时间的最小时间} else {// 已有种子就直接返回最短时间return Min[t];//找过直接返回}}}class zajiao {// (a,b)->cpublic int a;public int b;public int c;public zajiao(int a, int b, int c) {this.a = a;this.b = b;this.c = c;}}