1. 题目描述
2. 思路
建图
最短路应该是可以看出来的，但是对于给定的规则，作物 \(a\) 和作物 \(b\) 杂交产生种子 \(c\)，花费作物 \(a\) 和作物 \(b\) 成熟时间的最大值，我们如何根据这条规则建立边呢？
其实这也没什么好解释的，下面直接告诉你答案：
a -> c，边权为 b
b -> c，边权为 a
值得注意的是，这里的边权并不是传统意义上的边权，它代指一个条件。
\(b\) 到 \(c\) 的边权为 \(a\) 表示：\(b\) 只有满足拥有 \(a\) 的条件，才能到达（与 \(a\) 杂交产生） \(c\)。同理，
\(a\) 到 \(c\) 的边权为 \(b\) 表示，\(a\) 只有满足拥有 \(b\) 的条件，才能到达（与 \(b\) 杂交产生）\(c\)。
而真正的边权，就是 max(cost[a], cost[b])，这里的 cost[a] 就是题目给定的作物 \(a\) 成熟的时间。
所以说，通过本题，你应该明白如下结论：
边不止可以存储边权，还可以存储其他前驱结点以及其他的信息
抽象出问题的模型并建图往往是最难的！
求解
好了，现在我们已经建立了一个图，接下来该如下求解呢？
题目给定了我们一些初始作物，要求我们求目标作物，经典的 N -> 1 问题啊！你应该立马想到，将 N 抽象为 1（通过虚拟源点），然后就是求单源最短路！
由于边权都是正值，因此 \(dijkstra\) 和 \(spfa\) 都是可行的。
3. 代码(dijkstra)
4. 参考
标签：杂交,--,边权,dijkstra,建图,给定,AcWing3305,作物 From： https://www.cnblogs.com/ALaterStart/p/17215705.html