Dotcpp  >  编程题库  >  蓝桥杯2020年第十一届省赛真题-作物杂交
题目 2590:

蓝桥杯2020年第十一届省赛真题-作物杂交

时间限制: 2s 内存限制: 192MB 提交: 837 解决: 279

题目描述

作物杂交是作物栽培中重要的一步。已知有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, 保证目标种子一定可以通过杂交得到。

标签