目录
一、题目
【提炼版本如下】：
在一个农业实验室中，科学家正在研究作物的杂交方案。已知：
初始作物：共有
m种作物，可以直接种植。杂交方案：共有
k种杂交方案，每种方案可以将两个已有作物杂交出一种新作物（杂交时取作物的最长时间，作物之间可以同时进行杂交）。生长时间：每种作物
i需要w[i]单位时间才能成熟。目标：科学家希望培育出第
t号作物，请计算最短所需时间。
二、思路
本题是一个有向无环图（DAG）上的最短路径问题，可以使用记忆化搜索 + 动态规划求解
建立有向图：构建作物的杂交依赖关系，即
fa[c]记录生成c需要的a和b。递归计算作物生长时间：
若作物
t已经存在，直接返回0。若作物
t需要杂交，则递归计算a和b所需时间，并取最大值。更新
f[t] = min(f[t], max(生长时间[w[a], w[b]], 递归计算出的杂交时间))，表示t作物最早成熟的时间
【注意】：递归时注意记忆化保存已经得出的结果，避免重复计算，这是动态规划使用递归求解时一大重要特征，即记忆化保存结果
【理解】：得到结点c需要结点a、b，得到结点a、b也需要结点，于是不断向下，寻求子问题的解（此时我们便不能把结点a、b看作孤立的结点，而是看作一个封装好的函数，函数的结果是得到a、b花费的最小时间，也就是我们所说的递归）
三、代码
1. 变量定义
const int N = 2010;
typedef pair<int, int> PII;
int w[N], f[N]; //w[i]:作物i的成熟时间, f[i]:种植出i所需的最短时间
bool have[N]; //have[i]:是否已经拥有作物 i
vector<PII> fa[N]; //fa[i]:能杂交出作物i的作物对
w[i]：存储作物i需要的生长时间。f[i]：存储i号作物的最短培育时间，初始化为一个极大值。have[i]：用于标记i号作物是否是初始可用的。fa[c]：用于存储生成c所需的两个作物(a, b)，可能有多种杂交方案。
2. 递归求解作物最短生长时间
int dfs(int t)
{
for(int i = 0; i < fa[t].size(); i++)
{
int a = fa[t][i].first, b = fa[t][i].second;
if(!have[a]) dfs(a); //递归计算 A的最小种植时间
if(!have[b]) dfs(b); //递归计算B的最小种植时间
if(have[a] && have[b]) //只有当A和B都已经获取时,才能杂交得到 t
{
have[t] = true;
f[t] = min(f[t], max(w[a], w[b]) + max(f[a], f[b]));
//计算t的最早获得时间：
//-max(w[a], w[b]) 取决于A和B中更长的种植时间（因为种植时间取决于更慢的那个）
//-max(f[a], f[b]) 取决于A和B中更晚获得的时间（需要等它们都可用）
//-两者之和得到当前杂交方式的时间，再更新f[t]的最小值
}
}
return f[t];
}递归终止条件：
如果
t已经存在（have[t] == true），直接返回f[t]。
计算
t号作物的生长时间：遍历
fa[t]，获取所有可能的(a, b)组合。递归求解
a和b的培育时间。更新
f[t]，使其等于 所有可能方案中的最小值。
注意：必须要在a、b的时间都求解出来以后我们才能对c进行更新
3. main 函数：输入处理
int main()
{
int n, m, k, t;
cin >> n >> m >> k >> t;
fill(f,f+N,INT_MAX);
for(int i = 1; i <= n; i++) cin >> w[i];
for(int i = 1; i <= m; i++)
{
int temp;
cin >> temp;
have[temp] = true;
f[temp] = 0; //直接可用,不需要额外时间获取
}
for(int i = 1; i <= k; i++)
{
int a, b, c;
cin >> a >> b >> c;
fa[c].push_back({a, b});
}
cout << dfs(t);
return 0;
}读取 作物生长时间 并存入
w[i]。读取 初始可用作物 并标记
have[i] = true。读取 杂交方案 并存入
fa[c]。
【完整代码如下】：
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <climits>
#include <cstring>
using namespace std;
const int N = 2010;
typedef pair<int, int> PII;
int w[N], f[N]; //w[i]:作物i的成熟时间, f[i]:种植出i所需的最短时间
bool have[N]; //have[i]:是否已经拥有作物 i
vector<PII> fa[N]; //fa[i]:能杂交出作物i的作物对
int dfs(int t)
{
for(int i = 0; i < fa[t].size(); i++)
{
int a = fa[t][i].first, b = fa[t][i].second;
if(!have[a]) dfs(a); //递归计算 A的最小种植时间
if(!have[b]) dfs(b); //递归计算B的最小种植时间
if(have[a] && have[b]) //只有当A和B都已经获取时,才能杂交得到 t
{
have[t] = true;
f[t] = min(f[t], max(w[a], w[b]) + max(f[a], f[b]));
//计算t的最早获得时间：
//-max(w[a], w[b]) 取决于A和B中更长的种植时间（因为种植时间取决于更慢的那个）
//-max(f[a], f[b]) 取决于A和B中更晚获得的时间（需要等它们都可用）
//-两者之和得到当前杂交方式的时间，再更新f[t]的最小值
}
}
return f[t];
}
int main()
{
int n, m, k, t;
cin >> n >> m >> k >> t;
fill(f,f+N,INT_MAX);
for(int i = 1; i <= n; i++) cin >> w[i];
for(int i = 1; i <= m; i++)
{
int temp;
cin >> temp;
have[temp] = true;
f[temp] = 0; //直接可用,不需要额外时间获取
}
for(int i = 1; i <= k; i++)
{
int a, b, c;
cin >> a >> b >> c;
fa[c].push_back({a, b});
}
cout << dfs(t);
return 0;
}
四、关键破题点
1. 递归 + 记忆化搜索
dfs(t)递归计算t号作物的最短生长时间。通过 递归计算所有依赖的作物生长时间，并存入
f[t]，避免重复计算。
2. 处理多种杂交方案
由于
fa[c]可能存储多个(a, b)组合，因此dfs(t)需要遍历fa[t]的所有方案，并取 最优解（最短时间）。
3. 多种作物可以同时培育
- 由于
max(f[a], f[b])计算了a和b并行生长的最长时间，所以a和b可以同时生长，保证了作物可以并行培育，而不是一个接一个等待完成。
五、时间复杂度
每个作物最多递归一次，时间复杂度接近
O(n + k)，其中：O(n)处理初始作物。O(k)处理杂交方案。O(n)遍历dfs(t)计算最短时间。
总复杂度：
O(n + k)，适用于n, k ≤ 2000的情况。
六、拓展
最短路径问题（Dijkstra / Floyd / SPFA）
本题可视作 DAG 最短路径问题，使用 记忆化搜索（DFS + DP） 解法。
拓扑排序求解 DAG 最短路径
本题可改为 拓扑排序 + DP 解法，以减少递归栈深度。
多源 BFS
若所有
m个作物可以同时生长，可用 多源 BFS 计算t号作物的最短时间。