#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int MAXN = 310;
const int MAXM = 1001000;
const int inf = 1<<28;
struct EDG{
    int to,next,cap;
    int cost;  //单价
}edg[MAXM];
int head[MAXN],eid;
int pre[MAXN], cost[MAXN] ; //点0~(n-1)

void init(){
    eid=0;
    memset(head,-1,sizeof(head));
}
void addEdg(int u,int v,int cap,int cst){
    edg[eid].to=v; edg[eid].next=head[u]; edg[eid].cost = cst;
    edg[eid].cap=cap;  head[u]=eid++;

    edg[eid].to=u; edg[eid].next=head[v]; edg[eid].cost = -cst;
    edg[eid].cap=0;  head[v]=eid++;
}

bool inq[MAXN];
int q[MAXM];
int sNode,eNode;
bool spfa(const int& n){
    int l=0 , r=0 , i;
    memset(inq,0,sizeof(inq));
    for(int i=1; i<n; ++i)
        cost[i]=inf;
    cost[sNode]=0; inq[sNode]=1; pre[sNode]=-1;
    q[r++]=sNode;
    while(l!=r){
        int u=q[l++];
        if(l==MAXN)l=0;
        inq[u]=0;
        i=head[u];
        while(~i ){
            int v=edg[i].to;
            if(edg[i].cap>0 && cost[v]>cost[u]+edg[i].cost){ //在满足可增流的情况下，最小花费
                cost[v] = cost[u]+edg[i].cost;
                pre[v]=i;   //记录路径上的边
                if(!inq[v]){
                    if(r==MAXN)r=0;
                    q[r++]=v;
                    inq[v]=1;
                }
            }
            i=edg[i].next;
        }
    }
    if(cost[eNode]==inf)return 0;
    return 1;    //判断有没有增广路
}
//反回的是最大流，最小花费为minCost
void minCost_maxFlow(int& minCost,int n){
    while(spfa(n)){
        minCost+=cost[eNode];
        int i=pre[eNode];
        while(~i){
            edg[i].cap-=1; edg[i^1].cap+=1;
            i=pre[edg[i^1].to];
        }
    }
}
inline void scanf(int& ans){
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();

    ans=0;
    while(ch>='0'&&ch<='9'){
        ans=ans*10+ch-'0';
        ch=getchar();
    }
}

int mapt[MAXN][MAXN],dis[MAXN][MAXN];
void spfa(int n,int m){
    queue<int>qt;
    bool inq[MAXN]={0};
    for(int i=m+1; i<=n+m; i++){  //港口
        for(int j=1; j<=m; j++)
            dis[i][j]=inf;
        dis[i][i]=0;
        qt.push(i);
        while(!qt.empty()){
            int u=qt.front(); qt.pop();
            inq[u]=0;
            for(int v=1; v<=m; v++)  //油田
                if(dis[i][v]>dis[i][u]+mapt[u][v]) {
                    dis[i][v]=dis[i][u]+mapt[u][v];
                    if(!inq[v])
                        inq[v]=1,qt.push(v);
                }
        }
    }
}
int main(){
    //输入，初始化init()
    int n,m,k,p,a,b,c;
    while(~scanf("%d%d%d%d",&n,&m,&k,&p)){

        init();
        for(int i=1; i<=n+m; i++)
            for(int j=1; j<=n+m; j++)
                mapt[i][j]=inf;

        sNode=0; eNode=n+m+1;
        int  i=1;
        while(i<=n){
            scanf(a);    // 般只所在的油田
            addEdg(sNode , a , 1 , 0);
            i++;
        }
        i=1;  while(i<=n) addEdg(i+m , eNode , 1 , 0),i++;

        while(k--){
            scanf(a);
            scanf(b);
            scanf(c);
            if(mapt[a][b]>c)
                mapt[a][b]=mapt[b][a]=c;
        }
        while(p--){
            scanf(a);   //港口
            scanf(b);
            scanf(c);
            if(mapt[a+m][b]>c)
                mapt[a+m][b]=c;
        }
        spfa(n,m);
        for(int u=1; u<=m; u++) //油田
            for(int v=m+1; v<=m+n; v++) //港口
            if(dis[v][u]!=inf)
             addEdg(u,v,1,dis[v][u]);
        int mincost=0;
        minCost_maxFlow( mincost, eNode+1);
        printf("%d\n",mincost);
    }
}

版权声明：本文为博主原创文章，未经博主允许不得转载。