题目
作物杂交是作物栽培中重要的一步。已知有 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, 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≤N≤2000, 2≤M≤ N, 1≤K≤10^5, 1≤T≤N 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
1 #include <iostream> 2 #include <algorithm> 3 #include "string.h" 4 #include <vector> 5 using namespace std; 6 7 struct parent //存储杂交方案 8 { 9 int x; 10 int y; 11 }; 12 int n, m, k, t, tmp; 13 long long plant_time[2005];//每种作物的种植时间 14 bool flag[2005];//标记是否出现了该作物 15 long long min_hybrid_time[2005];//杂交出每种作物的最短时间 16 vector< vector<parent> >hybrid(2005);//存储每种作物的所有杂交方案 17 18 long long solve(int now) 19 { 20 if (flag[now])//若是已有杂交出该种作物的最短时间 21 return min_hybrid_time[now];//直接返回即可 22 23 for (int i = 0; i < hybrid[now].size(); i++)//对能够杂交出当前作物的方案都尝试一下 24 { 25 parent tmp = hybrid[now][i];//能够杂交出当前作物的第i种方案 26 //当前作物的最短杂交时间是 杂交出该作物的所有方案 中的最短时间 27 //而每种方案的最短时间是种植其‘父母’作物所需要的时间 + 其父母作物杂交所需的的最短时间（=两者杂交所需时间中的最大值) 28 min_hybrid_time[now] = min(min_hybrid_time[now], max(plant_time[tmp.x], plant_time[tmp.y]) + max(solve(tmp.x), solve(tmp.y))); 29 } 30 flag[now] = true;//标记已经找到最短杂交时间 31 return min_hybrid_time[now];//返回最短杂交时间 32 } 33 34 int main() 35 { 36 cin >> n >> m >> k >> t; 37 memset(min_hybrid_time, 0x3f, sizeof(min_hybrid_time));//杂交出每种作物的最短时间初始化为最大值 38 memset(flag, false, sizeof(flag));//作物标记初始化 39 //注意作物的下标从1开始！！！ 40 for (int i = 1; i <= n; i++)//输入种植时间 41 cin >> plant_time[i]; 42 for (int i = 0; i < m; i++)//输入初始种子数据 43 { 44 cin >> tmp; 45 flag[tmp] = true;//标记已经有了最短杂交时间 46 min_hybrid_time[tmp] = 0;//最短杂交时间 = 0，因为不需要杂交 47 } 48 for (int i = 0; i < k; i++)//输入所有杂交方案 49 { 50 parent temp; 51 cin >> temp.x >> temp.y >> tmp; 52 hybrid[tmp].push_back(temp);//存储杂交方案 53 } 54 solve(t);//递归求解 55 cout << min_hybrid_time[t] << endl;//输出杂交出目标作物的最短时间 56 return 0; 57 }
本来想法是二叉树，发现不一定只有两个分叉，所以不符合（不过能写出来很好啦）
然后想还是深度优先搜索和动态规划！！！
第28行yyds！！！仔细理解