题目链接：
题目描述
作物杂交是作物栽培中重要的一步。已知有 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 stub Scanner 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)->c public 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; } }
