fa[u] = {x, y};//存节点u的所有杂交父节点对。
st[u] = 判断是否能到达;
f[u] 存到当前点的最小值，初始化为INF;

核心代码

int dfs(int u){
    st[u] = true;
    int len = fa[u].size();
    for(int i = 0; i < len; i ++ ){ // 枚举所有父节点对
        int x = fa[u][i].first, y = fa[u][i].second;
        if(!st[x]) dfs(x);
        if(!st[y]) dfs(y); // 在回溯时进行处理
        if(st[x] && st[y]){ // 只有当父节点对都能搞出来才更新
            st[u] = true;
            f[u] = min(f[u], max(f[x], f[y]) + max(w[x], w[y]));
            // 能够保证此时f[x], f[y]已经更新完毕
            // 有点记忆化搜索的感觉。
        }
    }
    return f[u];
}

这题的图虽然不是树，但是感觉就是用树形dp搞出来的，图可以抽象成具有树topo结构的图（感觉）。

完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2005, INF = 0x3f3f3f3f;
typedef pair<int, int > PII;
int n, m, k, t, w[N], f[N];
bool st[N];
vector<PII> fa[N];


int dfs(int u){
    st[u] = true;
    int len = fa[u].size();
    for(int i = 0; i < len; i ++ ){
        int x = fa[u][i].first, y = fa[u][i].second;
        if(!st[x]) dfs(x);
        if(!st[y]) dfs(y);
        if(st[x] && st[y]){
            st[u] = true;
            f[u] = min(f[u], max(f[x], f[y]) + max(w[x], w[y]));
        }
    }
    return f[u];
}

int main(){
    memset(f, 0x3f, sizeof f);
    cin >> n >> m >> k >> t;
    for(int i = 1; i <= n; i ++ ) cin >> w[i];
    for(int i = 1; i <= m; i ++ ){
        int x;
        cin >> x;
        st[x] = true;
        f[x] = 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) << endl;

    return 0;
}