一、题目
1、原题链接
3305. 作物杂交
2、题目描述
作物杂交是作物栽培中重要的一步。
已知有 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。
第 3 行包含 M 个整数，分别表示已拥有的种子类型 Kj，Kj 两两不同。
第 4 至 K+3 行，每行包含 3 个整数 A,B,C，表示第 A 类作物和第 B 类作物杂交可以获得第 C 类作物的种子。
输出格式
输出一个整数，表示得到目标种子的最短杂交时间。
样例解释
1≤N≤2000,2≤M≤N,1≤K≤105,1≤T≤N,1≤Ti≤100,1≤Kj≤M,
保证目标种子一定可以通过杂交得到。
不保证作物 A 和 B 杂交只能生成作物 C（也就是说，A×B→C 和 A×B→D 可能同时在输入中出现）
不保证作物 C 只能由作物 A 和 B 杂交生成（也就是说，A×B→D 和 A×C→D 可能同时在输入中出现）。
不保证同一杂交公式不在输入中重复出现。
输入样例：
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
样例解释
第 1 天至第 5 天，将编号 1 与编号 2 的作物杂交，得到编号 3 的作物种子。
第 6 天至第 10 天，将编号 1 与编号 3 的作物杂交，得到编号 4 的作物种子。
第 6 天至第 9 天，将编号 2 与编号 3 的作物杂交，得到编号 5 的作物种子。
第 11 天至第 16 天，将编号 4 与编号 5 的作物杂交，得到编号 6 的作物种子。
总共花费 16 天。
二、解题报告
1、思路分析
思路来源：y总讲解视频
y总yyds
动态规划解法（spfa思想求解）
（1）dist数组含义：dist[i][j]表示在杂交次数小于等于i的方法中，生成j所需花费的最小时间。
（2）按最后一次的杂交方式进行划分，最多可以分为k种。
（3）转移方程：当最后一次杂交（假设为A、B杂交）确定后，要使总时间最小，则使将A、B都生成所花费的时间最小即可。即 dist[i][j]=max(dist[i-1][A],dist[i-1][B])+max(T[A],T[B])（T[i]代表生成i需要花费的时间）。
（4）利用spfa进行优化：只有一个点被更新过才需要利用它来更新其他点，并且dist[][]的第一维可以被优化。
（5）利用上述思路进行模拟即可，输出dist[t]即为答案。
2、时间复杂度
时间复杂度为O(n*k)
3、代码详解
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=2010,M=200010; //N代表点数（作物数），M代表边数，每种作物最多可能有k种杂交方式，所以M开成N*k数量级
int h[N],e[M],ne[M],w[N],target[M],idx; //类似邻接表存储所有的杂交方式，w[]存储生成每种作物需要花费的时间，target[i]存储利用i杂交可以生成的目标种子，w[i]存储生成i需要的时间
int n,m,k,t;
int dist[N];
bool st[N];
queue<int> q;
//类似邻接表加边
void add(int a,int b,int c){
e[idx]=b;
target[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
//spfa思路来填充dist数组
void spfa(){
while(!q.empty()){
int A=q.front();
q.pop();
st[A]=false;
for(int i=h[A];i!=-1;i=ne[i]){
int B=e[i],T=target[i];
if(dist[T]>max(dist[A],dist[B])+max(w[A],w[B])){
dist[T]=max(dist[A],dist[B])+max(w[A],w[B]);
if(!st[T]){
st[T]=true;
q.push(T);
}
}
}
}
}
int main(){
cin>>n>>m>>k>>t;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++){
cin>>w[i];
}
memset(dist,0x3f,sizeof dist);
while(m--){
int x;
cin>>x;
dist[x]=0; //初始作物已有，不需要生成，所以生成时间为0
st[x]=true;
q.push(x);
}
while(k--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c); //因为填充dist[a]和dist[b]时都需要知道利用它的杂交方式，所以得是无向边，便于访问
add(b,a,c);
}
spfa();
cout<<dist[t];
return 0;
}
三、知识风暴
Spfa算法
spfa算法为队列优化的Bellman-Ford算法。
基本思想：在Bellman-Ford算法基础上，不是每次都进行松弛操作（如果存在边(a,b,c)，即a到b的边且边权为c，而且dist[a]>dist[b]+c（dist[i]存储1号点到i号点的最短路径的长度）即可进行松弛），而是如果一个点被更新过，将它加入队列中，然后利用它来松弛其他点，然后将该点弹出，再将更新过的点加入队列中，循环往复，直到队列为空，算法结束。
