蓝桥杯——作物杂交 （java）

题目描述

作物杂交是作物栽培中重要的一步。已知有 NN 种作物 (编号 11 至 NN )，第 ii 种作物从播种到成熟的时间为 T_iTi​。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天，作物 B 种植时间为 7 天，则 AB 杂交花费的时间为 7 天。作物杂交会产生固定的作物，新产生的作物仍然属于 NN 种作物中的一种。

初始时，拥有其中 MM 种作物的种子 (数量无限，可以支持多次杂交)。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。

如存在 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, TN,M,K,T，NN 表示作物种类总数 (编号 11 至 NN)，MM 表示初始拥有的作物种子类型数量，KK 表示可以杂交的方案数，TT 表示目标种子的编号。

第 2 行包含 NN 个整数，其中第 ii 个整数表示第 ii 种作物的种植时间 T_i\ (1 \leq T_i \leq 100)Ti​ (1≤Ti​≤100)。

第 3 行包含 MM 个整数，分别表示已拥有的种子类型 K_j\ (1 \leq K_j \leq M)Kj​ (1≤Kj​≤M)，K_jKj​ 两两不同。

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

其中，1 \leq N \leq 2000, 2 \leq M \leq N, 1 \leq K \leq 10^5, 1 \leq T \leq N1≤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;

public class 作物杂交 {
    static int n, m, k, t;
    //种植时间、初始作物种类、杂交所需的时间、植物是否已经合成、记录各类物种合成所需的最短时间
    static int[] time, staSeed, maxTime, visited, res;
    static int[][] hyb;//杂交途径

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        //第一行数目
        n = scan.nextInt();//作物种类
        m = scan.nextInt();//初始作物种类
        k = scan.nextInt();//杂交途径
        t = scan.nextInt();//目标种子
        res = new int[n + 1];
        time = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            time[i] = scan.nextInt();
        }
        staSeed = new int[m];//初始作物种类
        maxTime = new int[k];
        visited = new int[n + 1];
        for (int i = 0; i < m; i++) {
            staSeed[i] = scan.nextInt();
            visited[staSeed[i]] = 1;//记录初始作物已合成
        }
        hyb = new int[k][3];
        for (int i = 0; i < k; i++) {
            hyb[i][0] = scan.nextInt();
            hyb[i][1] = scan.nextInt();
            hyb[i][2] = scan.nextInt();
            maxTime[i] = Math.max(time[hyb[i][0]], time[hyb[i][1]]);
        }

        System.out.println(dfs(t));
    }

    public static int dfs(int tar) {//kx：
        if (visited[tar] == 0) {//未合成
            int min = Integer.MAX_VALUE;
            //遍历杂交hyb
            for (int i = 0; i < k; i++) {
                if (hyb[i][2] == tar) {
                    min = Math.min(min, (maxTime[i] + Math.max(dfs(hyb[i][0]), dfs(hyb[i][1]))));
                }
            }
            visited[tar] = 1;
            res[tar] = min;
            return min;
        } else {
            return res[tar];
        }
    }
}