蓝桥杯-作物杂交（C++）
题目描述
作物杂交是作物栽培中重要的一步。已知有 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
解题思路：
首先要注意一点：产生某种种子的杂交方案可能不止一种，我一开始就是没考虑这点，所以测试数据一个都没通过。
以题目给出的样例来解释：我们要得到6号种子，就要先得到4号种子和5号种子；所以问题就分解为求4号种子和5号种子的最短杂交时间；然后，我们要得到4号种子，就要先得到1号种子和3号种子，这里1号种子最初就已经有了，所以我们记1号种子的最短杂交时间为0；要得到3号种子，就要先得到1号种子和2号种子，而这两种种子的最短杂交时间已经有了（这里都是0），所以计算（计算时要用到种植时间）得出3号种子的最短杂交时间；这时候1号种子和3号种子的最短杂交时间都已经有了，所以我们可以计算得出4号种子的最短杂交时间；对5号种子也是如此，最后可以计算得到6号种子的最短杂交时间。
这里要用到递归和回溯的思想。另外，对于某种种子，若求出了它的最短杂交时间，我们就将其保存下来，这样可以避免后续多余的计算，大幅节省时间。
再强调一次：上述样例中，得到3、4、5、6号种子的杂交方案均只有一种，但实际上，可以有很多种，解题时要考虑每种方案，并取时间最短的那个。
程序代码：
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
const int maxn = 2010;
int N, M, K, T;
vector<int>times(maxn); //保存种子的种植时间
vector<int>early(maxn, -1); //保存种子的最短杂交时间（初始化为-1）
vector<int>part[maxn]; //保存产生种子i的杂交方案（很可能大于一种）
int DFS(int target);
int main()
{
cin >> N >> M >> K >> T;
for (int i = 1; i <= N; i++) {
cin >> times[i];
}
int m;
for (int i = 1; i <= M; i++) {
cin >> m;
early[m] = 0; //对于原本就有的种子，最短杂交时间设为0
}
int a1, a2, a3;
for (int i = 1; i <= K; i++) {
cin >> a1 >> a2 >> a3;
//每两个数为一组杂交方案
part[a3].push_back(a1);
part[a3].push_back(a2);
}
int ans = DFS(T);
cout << ans << endl;
return 0;
}
int DFS(int target)
{
int a, b;
early[target] = 1e9;
//杂交方案可能不止一种，要求出所有方案，再选择最优的
for (int i = 0; i + 1 < part[target].size(); i += 2) {
//a，b两个数构成一个杂交方案
a = part[target][i];
b = part[target][i + 1];
if (early[a] == -1) {
//求a的最短杂交时间
early[a] = DFS(a);
}
if (early[b] == -1) {
//求b的最短杂交时间
early[b] = DFS(b);
}
//选择最优的杂交方案
early[target] = min(early[target], max(times[a], times[b]) + max(early[a], early[b]));
}
return early[target];
}
以上便是我对这道题的看法，很高兴与大家分享。