作物杂交

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 2000 + 5;
int n, m, k, goal;
int t[N];
bool ori[N];
int to[N][N];
int limit_time;
struct father {
    int num;
    int u[N];
    int v[N];
    int limtime;
} fa[N];
void input() {
    // N,M,K,T，
    // N 表示作物种类总数 (编号 1 至 N)，
    // M 表示初始拥有的作物种子类型数量，
    // K 表示可以杂交的方案数，T 表示目标种子的编号。
    cin >> n >> m >> k >> goal;
    for (int i = 1; i <= n; i++) cin >> t[i];
    for (int i = 1, z; i <= m; i++) {
        cin >> z;
        ori[z] = true;
    }
    for (int i = 1, u, v, w; i <= k; i++) {
        cin >> u >> v >> w;
        to[u][v] = to[v][u] = w;
        int x = ++fa[w].num;
        if (t[u] < t[v]) swap(u, v);
        fa[w].u[x] = u;
        fa[w].v[x] = v;
    }
}
bool dfs(int x) {
    if (fa[x].num == 0) return false;
    for (int i = 1; i <= fa[x].num; i++) {
        int v = fa[x].v[i];
        int u = fa[x].u[i];
        if (!ori[u]) {
            if (!dfs(u)) continue;
        }
        if (!ori[v]) {
            if (!dfs(v)) continue;
        }
        if (!fa[x].limtime)
            fa[x].limtime = max(fa[u].limtime, fa[v].limtime) + max(t[u], t[v]);
        else
            fa[x].limtime =
                min(fa[x].limtime,
                    max(fa[u].limtime, fa[v].limtime) + max(t[u], t[v]));
    }
    ori[x] = true;
    return true;
}
int main() {
    input();
    dfs(goal);
    cout << fa[goal].limtime;
    return 0;
}