目录
题目描述
作物杂交是作物栽培中重要的一步。已知有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(1≤Ti≤100)。第3行包含 M个整数，分别表示已拥有的种子类型 Kj(1≤Kj≤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天。
评测用例规模与约定
对于所有评测用例，1≤N≤2000, 2≤M≤N, 1≤K≤100000, 1≤T≤N, 保证目标种子一定可以通过杂交得到。
原题链接
题目 2590: 蓝桥杯2020年第十一届省赛真题-作物杂交
https://www.dotcpp.com/oj/problem2590.html
代码思路
import java.util.Scanner;
public class Main{
static int N;
static int M;
static int K;
static int T;
static int Ti[];
static boolean Kj[];
static int hybridize[][];
static int optimize[];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
N = scanner.nextInt();// 作物种类总数
M = scanner.nextInt();// 初始拥有的作物种子类型数量
K = scanner.nextInt();// 可以杂交的方案数
T = scanner.nextInt() - 1;// 目标种子的编号
Ti = new int[N];// 作物的种植时间
Kj = new boolean[N];// 已拥有的种子类型数量
hybridize = new int[K][4];// 杂交的方案和杂交的时间
optimize = new int[N];// 储存已经得到的值,避免重复
for (int i = 0; i < N; i++) {
Ti[i] = scanner.nextInt();
}
for (int i = 0; i < M; i++) {
Kj[scanner.nextInt() - 1] = true;
}
for (int i = 0; i < K; i++) {
hybridize[i][0] = scanner.nextInt() - 1;
hybridize[i][1] = scanner.nextInt() - 1;
hybridize[i][2] = scanner.nextInt() - 1;
hybridize[i][3] = Math.max(Ti[hybridize[i][0]], Ti[hybridize[i][1]]);// 这个作物的杂交时间
}
System.out.println(dfs(T));
}
static int dfs(int T) {
int min = Integer.MAX_VALUE;
if (!Kj[T]) {
for (int i = 0; i < K; i++) {
if (hybridize[i][2] == T) {
// Math.max的作用是:从起始开始算,获得种子的时间取最大的(dfs()这个函数会递归到初始种子)
// Math.min的作用是:有很多方案获得这个种子,取最小的时间
min = Math.min(min, hybridize[i][3] + Math.max(dfs(hybridize[i][0]), dfs(hybridize[i][1])));
}
}
optimize[T] = min;// 避免重复的查找
Kj[T] = true;// 避免重复的查找
return min;
} else {
return optimize[T];// 拥有这个种子类型,则返回得到这个种子的最小时间.
}
}
}
