AcWing
3305. 作物杂交
SPFA. SPFA与Dijkstra的区别是，SPFA可以用来搜索含负权边图的单源最短路径，但是不能包括负环(只能用来检测负环)；而Dijkstra只能用于非负权图。SPFA算法的时间复杂度在$O(kE)\sim O(VE)$，$k$为一个较小的常数，稀疏图上效率较高。一般来说，Dijkstra算法的时间复杂度比SPFA算法更稳定，Dijkstra算法(堆优化)能过的情况下，SPFA可以过掉大部分测试点。
SPFA算法是Bellman-Ford算法的一种优化，其算法思想基于动态规划(DP). 它维护一个队列，每次取出队首元素，visited变为0，遍历它的邻接点，对于被更新(dist更新为更小值)的点，如果它当前不在队列(visited为0)，则将其加入队列，visited变为1. 循环上述操作，直至队列为空。
对于本题，w表示种子生长的时间，e表示邻接点(配对点)，target表示杂交产生的点，M应该取二倍的杂交方案数，因为如果a与b可以配对，那么b与a也可以配对。本题也可以看作，已经拥有的种子连接了一个超级源点。
#include <bits/stdc++.h>
using namespace std;
int n, m, k, t;
const int N = 2010, M = 100010 * 2;
int w[N], h[N], e[M], target[M], ne[M], idx;
queue<int> q;
int dist[N];
bool visited[N];
void add(int a, int b, int c){
e[idx] = b, target[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void spfa(){
while(!q.empty()){
int top = q.front();
visited[top] = 0;
q.pop();
for(int i = h[top]; ~i; i = ne[i]){
int j = e[i];
if(max(dist[top], dist[j]) + max(w[top], w[j]) < dist[target[i]]){
dist[target[i]] = max(dist[top], dist[j]) + max(w[top], w[j]);
if(!visited[target[i]]) q.push(target[i]);
visited[target[i]] = 1;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cin.tie(0);
cin >> n >> m >> k >> t;
memset(h, -1, sizeof h);
memset(visited, false, sizeof visited);
memset(dist, 0x3f, sizeof dist);
for(int i = 1; i <= n; i++) cin >> w[i];
while(m--){
int temp;
cin >> temp;
q.push(temp);
visited[temp] = 1;
dist[temp] = 0;
}
while(k--){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
spfa();
cout << dist[t] << endl;
return 0;
}