作物杂交（JAVA）

题目：

作物杂交是作物栽培中重要的一步。已知有 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 类作物的种子。

其中， 1≤N≤2000,2≤M≤N,1≤K≤105,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

输出

16

样例说明

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

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

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

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

总共花费 16 天。

运行限制
最大运行时间：2s
最大运行内存: 256M

代码：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
 
public class Main {
    static int N,M,K,T;     
    static int[] time;         //time数组记录每个作物的成熟时间
    static boolean[] flag;     //用boolean类型的数组记录是否拥有某个作物的种子拥有记为true
    static int[][] line;       //line为一个K行3列的二维数组用于存储合成方案
    static  int [] maxtime;    //用于存储每种作物杂交所需要的成熟时间
    static int[] res;          //用于存储每种作物最终合成所需要的最终时间
 
 
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
 
        N=scan.nextInt();
        M=scan.nextInt();
        K=scan.nextInt();
        T=scan.nextInt();           //第一行输入
        time=new int[N+1];
        flag=new boolean[N+1];
        line=new int[K][3];
        maxtime=new int[K];
        res=new int[N+1];
        for (int i=1;i<N+1;i++){
            time[i]=scan.nextInt();  //第二行输入
        }
 
        for (int i=0;i<M;i++){
            int seed = scan.nextInt();
            flag[seed] = true;
        }                             //第三行输入
        for (int i=0;i<K;i++) {
            line[i][0]=scan.nextInt(); // A
            line[i][1]=scan.nextInt(); // B
            line[i][2]=scan.nextInt(); // C
            maxtime[i]=Math.max(time[line[i][0]],time[line[i][1]]);
        }                              //第四行输入
        System.out.println(time(T));
        scan.close();
 
 
    }
    public static int time(int index){   
        if (flag[index]==false){
           int expend=Integer.MAX_VALUE;  //记录时间选取最小值初始值为Integer.MAX_VALUE（表示int数据类型的最大取值数：2 147 483 647）防止在第一次比较时造成干扰
           for (int i=0;i<K;i++){
               if (line[i][2]==index){
                   expend=Math.min(maxtime[i]+Math.max(time(line[i][0]),time(line[i][1])),expend);
               }
           }
           flag[index]=true;
           res[index]=expend;
 
        }
        return res[index];
    }                              //time方法遍历加递归得出合成目标作物所需要的时间
}