作物杂交

难点在于建图上，当需要杂交出一棵AxB -> C时，首先A要出现过，B也要出现过，所以在建图时要维护这两个信息

import java.io.*;
import java.util.*;

public class Main{
    static int N = 2010,M = 1000010;
    static int[] h = new int[N],ne = new int[M],
    w = new int[M],dis = new int[N],val = new int[M];
    static int[][] e = new int[M][3];
    static boolean[] st = new boolean[N];
    static int n,m,k,T,idx = 0,INF = 0x3f3f3f3f;
    public static void main(String[] args)throws IOException{
        BufferedReader br 
            = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        Arrays.fill(h,-1);
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);
        T = Integer.parseInt(s[3]);
        s = br.readLine().split(" ");
        for(int i = 1;i<=n;i++)
            val[i] = Integer.parseInt(s[i-1]);
        s = br.readLine().split(" ");
        for(int i = 1;i<=m;i++){
            int a = Integer.parseInt(s[i-1]);
            //建立虚拟原点
            add(0,0,a,0);
        }

        for(int i = 1;i<=k;i++){
            s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]),
            b = Integer.parseInt(s[1]),
            c = Integer.parseInt(s[2]);
            int edge = Math.max(val[a],val[b]);
            add(a,b,c,edge);
            add(b,a,c,edge);
        }

        dijkstra();

        System.out.println(dis[T]);

    }
    public static void dijkstra(){
        Arrays.fill(dis,INF);
        PriorityQueue<int[]> pq 
            = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
        pq.add(new int[]{0,0});
        dis[0] = 0;
        while(!pq.isEmpty()){
            int[] t = pq.poll();
            int ver = t[0];
            if(st[ver]) continue;
            st[ver] = true;
           // System.out.println(ver+" "+dis[ver]);
            for(int i = h[ver];i!=-1;i = ne[i]){
                int[] b = e[i];
                int a1 = b[0],a2 = b[1],j = b[2];
                //要种出j，a1和a2都必须种出过或者本身存在
                int d = Math.max(dis[a1],dis[a2]);
                if(dis[a1]<INF&&dis[a2]<INF&&d+w[i]<dis[j]){
                    dis[j] = d+w[i];
                    pq.add(new int[]{j,dis[j]});
                }
            }
        }
    }
    public static void add(int a1,int a2,int b,int c){
    //维护作物的两个父亲
        e[idx] = new int[]{a1,a2,b};
        ne[idx] = h[a1];
        w[idx] = c;
        h[a1] = idx++;
    }
}