题意

一个联通图里给定若干个点，求他们到某点距离之和的最小值。

题解

枚举到的某点，然后优先队列优化的dijkstra求最短路，把给定的点到其的最短路加起来，更新最小值。复杂度是\(O(NElogE)\)。

注意此题给的n是奶牛个数，p是牧场个数，p才是点的个数N，所以head、dis、vis要开到1000。

代码

/*

USER:19flipp1

TASK:butter

LANG:C++

*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define in(s) freopen(#s".in","r",stdin);freopen(#s".out","w",stdout);

#define ll long long

#define N 1005

#define M 3000

#define inf 0x3f3f3f3f

using namespace std;

int n,p,c,pos[N];

struct edge{

    int to,next,w;

}e[M];

int head[N],cnt;

void add(int u,int v,int w){

    e[cnt]=edge{v,head[u],w};

    head[u]=cnt++;

}

struct qnode{

    int v,c;

    int operator<(const qnode& r)const{

        return c>r.c;

    }

};

int d[N],vis[N];

int dijkstra(int s){

    for(int i=1;i<=p;i++){d[i]=inf;vis[i]=0;}

    priority_queue<qnode>que;

    while(!que.empty())que.pop();

    d[s]=0;

    que.push((qnode){s,0});

    while(!que.empty()){

        int u=que.top().v;

        que.pop();

        if(vis[u])continue;

        vis[u]=1;

        for(int i=head[u];~i;i=e[i].next){

            int v=e[i].to,w=e[i].w;

            if(!vis[v]&&d[v]>d[u]+w){

                d[v]=d[u]+w;

                que.push((qnode){v,d[v]});

            }

        }

    }

    int ans=0;

    for(int i=1;i<=n;i++)ans+=d[pos[i]];

    return ans;

}

int main(){

    in(butter);

    memset(head,-1,sizeof head);

    scanf("%d%d%d",&n,&p,&c);

    for(int i=1;i<=n;i++)scanf("%d",&pos[i]);

    for(int i=1;i<=c;i++){

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

        add(v,u,w);

    }

    int ans=inf;

    for(int i=1;i<=p;i++){

        int tans=dijkstra(i);

        ans=min(ans,tans);

    }

    printf("%d\n",ans);

    return 0;

}

/*

          P2

 P1 @--1--@ C1

     \    |\

      \   | \

       5  7  3

        \ |   \

         \|    \ C3

       C2 @--5--@

          P3    P4

*/